工件的释放时间和加工时间具有一致性的单机在线排序问题研究

工件的释放时间和加工时间具有一致性, 是指释放时间大的工件其加工时间不小于释放时间小的工件的加工时间, 即若$r_{i}\geq r_{j}$, 则$p_{i}\geq p_{j}$。本文在该一致性约束下, 研究最小化最大加权完工时间单机在线排序问题, 和最小化总加权完工时间单机在线排序问题, 并分别设计出$\frac{\sqrt{5}+1}{2}$-竞争的最好可能在线算法。     

A fast algorithm for the recursive calculation of dominant singular subspaces

In many engineering applications it is required to compute the dominant subspace of a matrix A   of dimension m×n$m\times n$, with m?n$m?n$. Often the matrix A is produced incrementally, so all the columns are not available simultaneously. This problem arises, e.g., in image processing, where each column of the matrix A represents an image of a given sequence leading to a singular value decomposition-based compression [S. Chandrasekaran, B.S. Manjunath, Y.F. Wang, J. Winkeler, H. Zhang, An eigenspace update algorithm for image analysis, Graphical Models and Image Process. 59 (5) (1997) 321–332]. Furthermore, the so-called proper orthogonal decomposition approximation uses the left dominant subspace of a matrix A where a column consists of a time instance of the solution of an evolution equation, e.g., the flow field from a fluid dynamics simulation. Since these flow fields tend to be very large, only a small number can be stored efficiently during the simulation, and therefore an incremental approach is useful [P. Van Dooren, Gramian based model reduction of large-scale dynamical systems, in: Numerical Analysis 1999, Chapman & Hall, CRC Press, London, Boca Raton, FL, 2000, pp. 231–247].     

Convergence of a recursive robust algorithm with strongly regular observations

Robust estimation of parameters may be obtained via stochastic approximation algorithms. This paper deals with the properties of a recursive estimator of a location parameter in a stationary strongly regular process. Adaptive estimators of particular interest are also studied.     

A method for constructing a recognition algorithm in algebra over an estimate calculation set

A method is proposed for constructing an algorithm in algebra over an estimate calculation set in an algebraic extension of the least degree.     

Implementation of a method for constructing a recognition algorithm in algebra over an estimate calculation set

A method is implemented for constructing an algorithm in algebra over an estimate calculation set in an algebraic extension of the least degree.     

Fast recursive algorithm for a class of structured matrices

In this paper, we continue the study of a class of structured matrices which may be treated as a generalization of the class of Hessenberg matrices. For this class fast recursive algorithms for solution of the corresponding linear systems are obtained. The implementation of algorithms is illustrated by numerical experiments.     

A note on the recursive calculation of dominant singular subspaces

A recursive procedure for computing an approximation of the left and right dominant singular subspaces of a given matrix is proposed in [1]. The method is particularly suited for matrices with many more rows than columns. The procedure consists of a few steps. In one of these steps a Householder transformation is multiplied to an upper triangular matrix. The following step consists in recomputing an upper triangular matrix from the latter product. In [1] it is said that the latter step is accomplished in O(k³) operations, where k is the order of the triangular matrix. In this short note we show that this step can be accomplished in O(k²) operations. This research was partially supported by MIUR, grant number 2002014121 (first author) and by the Research Council K.U.Leuven, project OT/00/16 (SLAP: Structured Linear Algebra Package), by the Fund for Scientific Research–Flanders (Belgium), projects G.0078.01 (SMA: Structured Matrices and their Applications), G.0176.02 (ANCILA: Asymptotic aNalysis of the Convergence behavior of Iterative methods in numerical Linear Algebra), G.0184.02 (CORFU: Constructive study of Orthogonal Functions) and G.0455.0 (RHPH: Riemann–Hilbert problems, random matrices and Padé–Hermite approximation), and by the Belgian Programme on Interuniversity Poles of Attraction, initiated by the Belgian State, Prime Ministers Office for Science, Technology and Culture, project IUAP V-22 (Dynamical Systems and Control: Computation, Identification & Modelling) (second and third author). The scientific responsibility rests with the authors.AMS subject classification 15A15, 15A09, 15A23     

Improvement of the Discrete Cosine Transform calculation by means of a recursive method

This paper presents a recursive method for function evaluation. The proposal argues for the use of a more complete primitive, namely a weighted sum, which converts the calculation of the function values into a recursive operation defined by a two input table. The weighted sum can be tuned for different values of the weighting parameters that hold the features of the concrete evaluated function. The calculation of the Discrete Cosine Transform (DCT) is improved by this method which provides a decrease of the operation count as well as an acceptable error bound. These results have repercussions on the compression standard JPEG, for the purposes of storage and transmission in web-based applications     

Extension of partial recursive functions and functions with a recursive graph

It is proved that every degree of complexity of mass problems, containing the decision problem of a recursive enumerable set, contains also the problem of extension of a partial recursive function, the graph of which is recursive. Some properties of functions with a recursive graph are considered.Translated from Matematicheskie Zametki, Vol. 5, No. 2, pp. 261–267, February, 1969.The author is deeply indebted to V. A. Uspenskii for discussion of the results.     

Comparison of splittings used with the conjugate gradient algorithm

We consider several possible criteria for comparing splittings used with the conjugate gradient algorithm. We present sharp upper bounds for the error at each step of the algorithm and compare several widely used splittings with respect to their effect on these sharp upper bounds. We then consider a more stringent comparison test, and present necessary and sufficient conditions for the error at each step with one splitting to be smaller than that with another, for all pairs of corresponding initial guesses.     

A Dai-Liao conjugate gradient algorithm with clustering of eigenvalues

A new value for the parameter in Dai and Liao conjugate gradient algorithm is presented. This is based on the clustering of eigenvalues of the matrix which determine the search direction of this algorithm. This value of the parameter lead us to a variant of the Dai and Liao algorithm which is more efficient and more robust than the variants of the same algorithm based on minimizing the condition number of the matrix associated to the search direction. Global convergence of this variant of the algorithm is briefly discussed.     

A trajectory algorithm based on the gradient method I. The search on the quasioptimal trajectories

The global optimization problem is considered under the assumption that the objective function is convex with respect to some variables. A finite subgradient algorithm for the search of an -optimal solution is proposed. Results of numerical experiments are presented.     

A gradient based iterative algorithm for solving model updating problems of gyroscopic systems

Model updating should be correlated with experimental data to ensure that it models the dynamics of the real structure and the updated model predicts the dynamics of a structure more accurately. Considering that the iterative methods for model updating have aroused little public attention, this paper studies an iterative algorithm for quadratic model updating problems which can incorporate the measured modal data into the finite element model to produce an adjusted finite element model on the mass, gyroscopic and stiffness matrices that closely match the experimental modal data. By this method, the best approximation symmetric and skew-symmetric solutions can be obtained by choosing a convergence factor. Numerical example shows that the introduced iterative algorithm is quite efficient.     

Interval-valued probability density estimation based on quasi-continuous histograms: Proof of the conjecture

The sensitivity of histogram computation to the choice of a reference interval and number of bins can be attenuated by replacing the crisp partition on which the histogram is built by a fuzzy partition. This involves replacing the crisp counting process by a distributed (weighted) voting process. The counterpart to this low sensitivity is some confusion in the count values: a value of 10 in the accumulator associated with a bin can mean 10 observations in the bin or 40 observations near the bin. This confusion can bias the statistical decision process based on such a histogram. In a recent paper, we proposed a method that links the probability measure associated with any subset of the reference interval with the accumulator values of a fuzzy partition-based histogram. The method consists of transferring counts associated with each bin proportionally to its interaction with the considered subset. Two methods have been proposed which are called precise and imprecise pignistic transfer. Imprecise pignistic transfer accounts for the interactivity of two consecutive cells in order to propagate, in the estimated probability measure, counting confusion due to fuzzy granulation. Imprecise pignistic transfer has been conjectured to include precise pignistic transfer. The present article proposes a proof of this conjecture.     

Equilibria of a stationary economy with recursive preferences

We consider an intertemporal stationary economy in discrete time, where agents have recursive preferences. Using dynamic programming, we show that equilibrium consumption trajectories from a capital stock are interior Pareto optima and are characterized by a strictly positive parameter in ^n–1, the set of agents' initial weights. We then exhibit prices that support the Pareto optima and use the Negishi method to characterize the parameters corresponding to equilibria. Finally, we prove the existence of equilibria and show that the number of regular equilibria is odd.     

On the number of lattice points in a small sphere and a recursive lattice decoding algorithm

Let L be a lattice in ${\mathbb{R}^n}$ . This paper provides two methods to obtain upper bounds on the number of points of L contained in a small sphere centered anywhere in ${\mathbb{R}^n}$ . The first method is based on the observation that if the sphere is sufficiently small then the lattice points contained in the sphere give rise to a spherical code with a certain minimum angle. The second method involves Gaussian measures on L in the sense of Banaszczyk (Math Ann 296:625–635, 1993). Examples where the obtained bounds are optimal include some root lattices in small dimensions and the Leech lattice. We also present a natural decoding algorithm for lattices constructed from lattices of smaller dimension, and apply our results on the number of lattice points in a small sphere to conclude on the performance of this algorithm.     

A novel algorithm based on parameterization method for calculation of curvature of the free surface flows

In this paper, a new approach based on parameterization method is presented for calculation of curvature on the free surface flows. In some phenomena such as droplet and bubble, surface tension is prominent. Therefore in these cases, accurate estimation of the curvature is vital. Volume of fluid (VOF) is a surface capturing method for free surface modeling. In this method, free surface curvature is calculated based on gradient of scalar transport parameter which is regarded as original method in this paper. However, calculation of curvature for a circle and other known geometries based on this method is not accurate. For instance, in practice curvature of a circle in interface cells is constant, while this method predicts different curvatures for it. In this research a novel algorithm based on parameterization method for improvement of the curvature calculation is presented. To show the application of parameterization method, two methods are employed. In the first approach denoted by, three line method, a curve is fitted to the free surface so that the distance between curve and linear interface approximation is minimized. In the second approach namely four point method, a curve is fitted to intersect points with grid lines for central and two neighboring cells. These approaches are treated as calculus of variation problems. Then, using the parameterization method, these cases are converted into the sequences of time-varying nonlinear programming problems. With some treatments a conventional equivalent model is obtained. It is finally proved that the solution of these sequences in the models tends to the solution of the calculus of variation problems. For verification of the presented methods, curvature of some geometrical shapes such as circle, elliptic and sinusoidal profile is calculated and compared with original method used in VOF process and analytical solutions. Finally, as a more practical problem, spurious currents are studied. The results showed that more accurate curve prediction is obtained by these approaches than the original method in VOF approach.     

Blossom V: a new implementation of a minimum cost perfect matching algorithm

We describe a new implementation of the Edmonds’s algorithm for computing a perfect matching of minimum cost, to which we refer as Blossom V. A key feature of our implementation is a combination of two ideas that were shown to be effective for this problem: the “variable dual updates” approach of Cook and Rohe (INFORMS J Comput 11(2):138–148, 1999) and the use of priority queues. We achieve this by maintaining an auxiliary graph whose nodes correspond to alternating trees in the Edmonds’s algorithm. While our use of priority queues does not improve the worst-case complexity, it appears to lead to an efficient technique. In the majority of our tests Blossom V outperformed previous implementations of Cook and Rohe (INFORMS J Comput 11(2):138–148, 1999) and Mehlhorn and Schäfer (J Algorithmics Exp (JEA) 7:4, 2002), sometimes by an order of magnitude. We also show that for large VLSI instances it is beneficial to update duals by solving a linear program, contrary to a conjecture by Cook and Rohe.     

A surface oriented solid formulation based on a hybrid Galerkin-collocation method

The contribution is concerned with a numerical method to analyze the mechanical behavior of 3D solids. The method employs directly the geometry defined by the boundary representation modeling technique, which is frequently used in CAD to define solids. It combines the benefits of the isogeometric analysis methodology with the scaled boundary finite element method. In the present approach, only the boundary surfaces of the solid are discretized. No tensor-product structure of three-dimensional objects is exploited to parametrize the physical domain. The weak form is applied only on the boundary surfaces. The governing partial differential equations of elasticity are transformed to an ordinary differential equation (ODE) of Euler type. The isogeometric Galerkin approach is employed to approximate the displacement response at the boundary surfaces. It exploits the two-dimensional NURBS objects to parametrize the boundary surfaces. To solve the Euler type ODE, the NURBS based collocation approach is applied. The accuracy of the method is validated against the analytical solutions. The presented method is able to analyze solids, which are bounded by an arbitrary number of surfaces. (© 2015 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Steganographic algorithm based on a chaotic map

In this paper, we suggest a new steganographic spatial domain algorithm based on a single chaotic map. Unlike most existing steganographic algorithms, the proposed algorithm uses one chaotic map to determine the pixel position of the host color image, the channel (red, green or blue) and the bit position of the targeted value in which a sensitive information bit can be hidden. Furthermore, this algorithm can be regarded as a variable-sized embedding algorithm. Experimental results demonstrate that this algorithm can defeat many existing steganalytic attacks. In comparison with existing steganographic spatial domain based algorithms, the suggested algorithm is shown to have some advantages over existing ones, namely, larger key space and a higher level of security against some existing attacks.