Preordering saddle‐point systems for sparse LDLT factorization without pivoting

This paper focuses on efficiently solving large sparse symmetric indefinite systems of linear equations in saddle‐point form using a fill‐reducing ordering technique with a direct solver. Row and column permutations partition the saddle‐point matrix into a block structure constituting a priori pivots of order 1 and 2. The partitioned matrix is compressed by treating each nonzero block as a single entry, and a fill‐reducing ordering is applied to the corresponding compressed graph. It is shown that, provided the saddle‐point matrix satisfies certain criteria, a block LDL^T factorization can be computed using the resulting pivot sequence without modification. Numerical results for a range of problems from practical applications using a modern sparse direct solver are presented to illustrate the effectiveness of the approach.     

Preconditioning Indefinite Systems in Interior Point Methods for Optimization

Every Newton step in an interior-point method for optimization requires a solution of a symmetric indefinite system of linear equations. Most of today's codes apply direct solution methods to perform this task. The use of logarithmic barriers in interior point methods causes unavoidable ill-conditioning of linear systems and, hence, iterative methods fail to provide sufficient accuracy unless appropriately preconditioned. Two types of preconditioners which use some form of incomplete Cholesky factorization for indefinite systems are proposed in this paper. Although they involve significantly sparser factorizations than those used in direct approaches they still capture most of the numerical properties of the preconditioned system. The spectral analysis of the preconditioned matrix is performed: for convex optimization problems all the eigenvalues of this matrix are strictly positive. Numerical results are given for a set of public domain large linearly constrained convex quadratic programming problems with sizes reaching tens of thousands of variables. The analysis of these results reveals that the solution times for such problems on a modern PC are measured in minutes when direct methods are used and drop to seconds when iterative methods with appropriate preconditioners are used.     

Vector and parallel computing for matrix balancing

Estimating the entries of a large matrix to satisfy a set of internal consistency relations is a problem with several applications in economics, urban and regional planning, transportation, statistics and other areas. It is known as theMatrix Balancing Problem. Matrix balancing applications arising from the estimation of telecommunication or transportation traffic and from multi-regional trade flows give rise to huge optimization problems. In this report, we show that the RAS algorithm can be specialized for vector and parallel computing and used for the solution of very large problems. The algorithm is specialized for vector computations on a CRAY X-MP and is parallelized on an Alliant FX/8. A variant of the algorithm — developed here for its potential parallelism — turns out to be more efficient than the original algorithm even when implemented serially. We use the algorithms to estimate disaggregated input/output tables and a multi-regional trade flow table of the U.S. The larger problem solved has approximately 12 000 constraints and over 370 000 nonlinear variables. This is the first of two papers that aim at the solution of very large matrix balancing problems. Zenios [20] is using the same algorithm for the same models on a massively parallel Connection Machine CM-2.Research partially supported by NSF grants ECS-8718971 and CCR-8811135, and AFOSR grant 89-0145. Computing resources were made available through the ACRF at Argonne National Laboratory and CRAY Research, Inc.     

A constraint-reduced variant of Mehrotra’s predictor-corrector algorithm

Consider linear programs in dual standard form with n constraints and m variables. When typical interior-point algorithms are used for the solution of such problems, updating the iterates, using direct methods for solving the linear systems and assuming a dense constraint matrix A, requires O(nm²)\mathcal{O}(nm^{2}) operations per iteration. When n≫m it is often the case that at each iteration most of the constraints are not very relevant for the construction of a good update and could be ignored to achieve computational savings. This idea was considered in the 1990s by Dantzig and Ye, Tone, Kaliski and Ye, den Hertog et al. and others. More recently, Tits et al. proposed a simple “constraint-reduction” scheme and proved global and local quadratic convergence for a dual-feasible primal-dual affine-scaling method modified according to that scheme. In the present work, similar convergence results are proved for a dual-feasible constraint-reduced variant of Mehrotra’s predictor-corrector algorithm, under less restrictive nondegeneracy assumptions. These stronger results extend to primal-dual affine scaling as a limiting case. Promising numerical results are reported.     

A fast direct solver for elliptic problems with a divergence constraint

A fast direct solution method for a discretized vector‐valued elliptic partial differential equation with a divergence constraint is considered. Such problems are typical in many disciplines such as fluid dynamics, elasticity and electromagnetics. The method requires the problem to be posed in a rectangle and boundary conditions to be either periodic boundary conditions or the so‐called slip boundary conditions in one co‐ordinate direction. The arising saddle‐point matrix has a separable form when bilinear finite elements are used in the discretization. Based on a result for so‐called p‐circulant matrices, the saddle‐point matrix can be transformed into a block‐diagonal form by fast Fourier transformations. Thus, the fast direct solver has the same structure as methods for scalar‐valued problems which are based on Fourier analysis and, therefore, it has the same computational cost ??(N log N). Numerical experiments demonstrate the good efficiency and accuracy of the proposed method. Copyright © 2002 John Wiley & Sons, Ltd.     

Cryptanalysis of Two McEliece Cryptosystems Based on Quasi-Cyclic Codes

We cryptanalyse here two variants of the McEliece cryptosystem based on quasi-cyclic codes. Both aim at reducing the key size by restricting the public and secret generator matrices to be in quasi-cyclic form. The first variant considers subcodes of a primitive BCH code. The aforementioned constraint on the public and secret keys implies to choose very structured permutations. We prove that this variant is not secure by producing many linear equations that the entries of the secret permutation matrix have to satisfy by using the fact that the secret code is a subcode of a known BCH code. This attack has been implemented and in all experiments we have performed the solution space of the linear system was of dimension one and revealed the permutation matrix. The other variant uses quasi-cyclic low density parity-check (LDPC) codes. This scheme was devised to be immune against general attacks working for McEliece type cryptosystems based on LDPC codes by choosing in the McEliece scheme more general one-to-one mappings than permutation matrices. We suggest here a structural attack exploiting the quasi-cyclic structure of the code and a certain weakness in the choice of the linear transformations that hide the generator matrix of the code. This cryptanalysis adopts a polynomial-oriented approach and basically consists in searching for two polynomials of low weight such that their product is a public polynomial. Our analysis shows that with high probability a parity-check matrix of a punctured version of the secret code can be recovered with time complexity O(n ³) where n is the length of the considered code. The complete reconstruction of the secret parity-check matrix of the quasi-cyclic LDPC codes requires the search of codewords of low weight which can be done with about 2³⁷ operations for the specific parameters proposed.     

Extrema of matrix functionals

The problem of determining conditional extrema of functionals with matrix arguments is considered. We derive the necessary and sufficient mathematical conditions for the existence of extrema of functionals satisfying constraints of the form of matrix equalities on the arguments. The construction of extrema is based on functions and matrices of indeterminate Lagrange multipliers. As applications we consider an example of determining the optimal strength coefficient matrix in a dynamical system with an adaptive Carleman filter and an example, from the theory of statistical decisions, of minimizing the volume of the dispersion error ellipsoid. Our approach has wide applications not only in optimization problems from automatic control theory but also in mathematical statistics and the theory of material strength and plasticity.Translated from Dinamicheskie Sistemy, No. 5, pp. 103–106, 1986.     

Adaptive constraint reduction for convex quadratic programming

We propose an adaptive, constraint-reduced, primal-dual interior-point algorithm for convex quadratic programming with many more inequality constraints than variables. We reduce the computational effort by assembling, instead of the exact normal-equation matrix, an approximate matrix from a well chosen index set which includes indices of constraints that seem to be most critical. Starting with a large portion of the constraints, our proposed scheme excludes more unnecessary constraints at later iterations. We provide proofs for the global convergence and the quadratic local convergence rate of an affine-scaling variant. Numerical experiments on random problems, on a data-fitting problem, and on a problem in array pattern synthesis show the effectiveness of the constraint reduction in decreasing the time per iteration without significantly affecting the number of iterations. We note that a similar constraint-reduction approach can be applied to algorithms of Mehrotra’s predictor-corrector type, although no convergence theory is supplied.     

Quadratic programming applications in finance using Excel

The paper describes two applications of quadratic programming in finance, one from the early years (Markowitz's efficient portfolios with minimum risk) and the other a more recent innovation (Sharpe's style analysis which estimates an implied asset allocation for an investment fund). We show how, in the presence of inequality constraints, Excel's Solver can be used to find the optimal weights in both quadratic programming applications. We also implement a direct analytic solution for generating the efficient frontier when there are no inequality constraints using the matrix functions in Excel. Both applications use only a small number of asset classes and require repeated use of the minimisation task. We show how Visual Basic for Applications (Microsoft's macro language for Excel) can be used to program such tasks, confirming that techniques that were the preserve of dedicated software only a few years ago can now be easily replicated using Excel to solve real problems.     

Solution of large‐scale weighted least‐squares problems

A sequence of least‐squares problems of the form min_y∥G^1/2(A^T y?h)∥₂, where G is an n×n positive‐definite diagonal weight matrix, and A an m×n (m?n) sparse matrix with some dense columns; has many applications in linear programming, electrical networks, elliptic boundary value problems, and structural analysis. We suggest low‐rank correction preconditioners for such problems, and a mixed solver (a combination of a direct solver and an iterative solver). The numerical results show that our technique for selecting the low‐rank correction matrix is very effective. Copyright © 2002 John Wiley & Sons, Ltd.     

Implicit QR algorithms for palindromic and even eigenvalue problems

In the spirit of the Hamiltonian QR algorithm and other bidirectional chasing algorithms, a structure-preserving variant of the implicit QR algorithm for palindromic eigenvalue problems is proposed. This new palindromic QR algorithm is strongly backward stable and requires less operations than the standard QZ algorithm, but is restricted to matrix classes where a preliminary reduction to structured Hessenberg form can be performed. By an extension of the implicit Q theorem, the palindromic QR algorithm is shown to be equivalent to a previously developed explicit version. Also, the classical convergence theory for the QR algorithm can be extended to prove local quadratic convergence. We briefly demonstrate how even eigenvalue problems can be addressed by similar techniques. D. S. Watkins partly supported by Deutsche Forschungsgemeinschaft through Matheon, the DFG Research Center Mathematics for key technologies in Berlin.     

Convex optimization problems involving finite autocorrelation sequences

 We discuss convex optimization problems in which some of the variables are constrained to be finite autocorrelation sequences. Problems of this form arise in signal processing and communications, and we describe applications in filter design and system identification. Autocorrelation constraints in optimization problems are often approximated by sampling the corresponding power spectral density, which results in a set of linear inequalities. They can also be cast as linear matrix inequalities via the Kalman-Yakubovich-Popov lemma. The linear matrix inequality formulation is exact, and results in convex optimization problems that can be solved using interior-point methods for semidefinite programming. However, it has an important drawback: to represent an autocorrelation sequence of length $n$, it requires the introduction of a large number ($n(n+1)/2$) of auxiliary variables. This results in a high computational cost when general-purpose semidefinite programming solvers are used. We present a more efficient implementation based on duality and on interior-point methods for convex problems with generalized linear inequalities. Received: August 20, 2001 / Accepted: July 16, 2002 Published online: September 27, 2002 RID="★" ID="★" This material is based upon work supported by the National Science Foundation under Grant No. ECS-9733450.     

Robust Frequency Estimation Using Elemental Sets

Abstract

The extraction of sinusoidal signals from time-series data is a classic problem of ongoing interest in the statistics and signal processing literatures. Obtaining least squares estimates is difficult because the sum of squares has local minima O(1/n) apart in the frequencies. In practice the frequencies are often estimated using ad hoc and inefficient methods. Problems of data quality have received little attention. An elemental set is a subset of the data containing the minimum number of points such that the unknown parameters in the model can be identified. This article shows that, using a variant of the classical method of Prony, parameter estimates for a sum of sinusoids can be obtained algebraically from an elemental set. Elemental set methods are used to construct finite algorithm estimators that approximately minimize the least squares, least trimmed sum of squares, or least median of squares criteria. The elemental set estimators prove able in simulations to resolve the frequencies to the correct local minima of the objective functions. When used as the first stage of an MM estimator, the constructed estimators based on the trimmed sum of squares and least median of squares criteria produce final estimators which have high breakdown properties and which are simultaneously efficient when no outliers are present. The approach can also be applied to sums of exponentials, and sums of damped sinusoids. The article includes simulations with one and two sinusoids and two data examples.     

A parallel radix‐4 block cyclic reduction algorithm

A conventional block cyclic reduction algorithm operates by halving the size of the linear system at each reduction step, that is, the algorithm is a radix‐2 method. An algorithm analogous to the block cyclic reduction known as the radix‐q partial solution variant of the cyclic reduction (PSCR) method allows the use of higher radix numbers and is thus more suitable for parallel architectures as it requires fever reduction steps. This paper presents an alternative and more intuitive way of deriving a radix‐4 block cyclic reduction method for systems with a coefficient matrix of the form tridiag{ ? I,D, ? I}. This is performed by modifying an existing radix‐2 block cyclic reduction method. The resulting algorithm is then parallelized by using the partial fraction technique. The parallel variant is demonstrated to be less computationally expensive when compared to the radix‐2 block cyclic reduction method in the sense that the total number of emerging subproblems is reduced. The method is also shown to be numerically stable and equivalent to the radix‐4 PSCR method. The numerical results archived correspond to the theoretical expectations. Copyright © 2013 John Wiley & Sons, Ltd.     

Direct and Inverse Eigenvalue Problems for Diagonal-Plus-Semiseparable Matrices

In this paper we study both direct and inverse eigenvalue problems for diagonal-plus-semiseparable (dpss) matrices. In particular, we show that the computation of the eigenvalues of a symmetric dpss matrix can be reduced by a congruence transformation to solving a generalized symmetric definite tridiagonal eigenproblem. Using this reduction, we devise a set of recurrence relations for evaluating the characteristic polynomial of a dpss matrix in a stable way at a linear time. This in turn allows us to apply divide-and-conquer eigenvalue solvers based on functional iterations directly to dpss matrices without performing any preliminary reduction into a tridiagonal form. In the second part of the paper, we exploit the structural properties of dpss matrices to solve the inverse eigenvalue problem of reconstructing a symmetric dpss matrix from its spectrum and some other informations. Finally, applications of our results to the computation of a QR factorization of a Cauchy matrix with real nodes are provided.     

An implicit QR algorithm for symmetric semiseparable matrices

The QR algorithm is one of the classical methods to compute the eigendecomposition of a matrix. If it is applied on a dense n × n matrix, this algorithm requires O(n³) operations per iteration step. To reduce this complexity for a symmetric matrix to O(n), the original matrix is first reduced to tridiagonal form using orthogonal similarity transformations. In the report (Report TW360, May 2003) a reduction from a symmetric matrix into a similar semiseparable one is described. In this paper a QR algorithm to compute the eigenvalues of semiseparable matrices is designed where each iteration step requires O(n) operations. Hence, combined with the reduction to semiseparable form, the eigenvalues of symmetric matrices can be computed via intermediate semiseparable matrices, instead of tridiagonal ones. The eigenvectors of the intermediate semiseparable matrix will be computed by applying inverse iteration to this matrix. This will be achieved by using an O(n) system solver, for semiseparable matrices. A combination of the previous steps leads to an algorithm for computing the eigenvalue decompositions of semiseparable matrices. Combined with the reduction of a symmetric matrix towards semiseparable form, this algorithm can also be used to calculate the eigenvalue decomposition of symmetric matrices. The presented algorithm has the same order of complexity as the tridiagonal approach, but has larger lower order terms. Numerical experiments illustrate the complexity and the numerical accuracy of the proposed method. Copyright © 2005 John Wiley & Sons, Ltd.     

Model reduction using the Vorobyev moment problem

Given a nonsingular complex matrix and complex vectors v and w of length N, one may wish to estimate the quadratic form w ^* A ^− 1 v, where w ^* denotes the conjugate transpose of w. This problem appears in many applications, and Gene Golub was the key figure in its investigations for decades. He focused mainly on the case A Hermitian positive definite (HPD) and emphasized the relationship of the algebraically formulated problems with classical topics in analysis - moments, orthogonal polynomials and quadrature. The essence of his view can be found in his contribution Matrix Computations and the Theory of Moments, given at the International Congress of Mathematicians in Zürich in 1994. As in many other areas, Gene Golub has inspired a long list of coauthors for work on the problem, and our contribution can also be seen as a consequence of his lasting inspiration. In this paper we will consider a general mathematical concept of matching moments model reduction, which as well as its use in many other applications, is the basis for the development of various approaches for estimation of the quadratic form above. The idea of model reduction via matching moments is well known and widely used in approximation of dynamical systems, but it goes back to Stieltjes, with some preceding work done by Chebyshev and Heine. The algebraic moment matching problem can for A HPD be formulated as a variant of the Stieltjes moment problem, and can be solved using Gauss-Christoffel quadrature. Using the operator moment problem suggested by Vorobyev, we will generalize model reduction based on matching moments to the non-Hermitian case in a straightforward way. Unlike in the model reduction literature, the presented proofs follow directly from the construction of the Vorobyev moment problem. The work was supported by the GAAS grant IAA100300802 and by the Institutional Research Plan AV0Z10300504.     

Aspects Regarding the Conception,Modeling and Implementation of an Articulated Robot in Space with Noises and Vibrations

The authors want to conceive and to model a structure of a 6R serial modular industrial robot with six freedom degrees. Some specific points are followed: the direct geometric modelling of the robot using the matrix of rotation method, the given in 3D modelling of the robot, the presentation of its components having some possible applications in the processes of production in the spaces with noises and vibrations. The direct geometrical modelling will be determinate the relative orientation matrices, which express the position of each system T_i, (i=1-6), according to the system T_i–1, also expressing the vectors of relative position of origin O_i of the systems T_i. They will be expressed the orientation of each system T_i in account to the fixed system T_o attached to the robot base, the set of independent parameters of orientation then are obtained the final equation of the column vector of the generalized coordinates, which express the position and the orientation of the clamping device. The paper presents the two possible applications of the studied robot implementation in a flexible manufacturing cel for the manipulation operations of parts. The robot will be used on the other side for the execution of weld in a points applied to the car carcases. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Sampling and multilevel coarsening algorithms for fast matrix approximations

This paper addresses matrix approximation problems for matrices that are large, sparse, and/or representations of large graphs. To tackle these problems, we consider algorithms that are based primarily on coarsening techniques, possibly combined with random sampling. A multilevel coarsening technique is proposed, which utilizes a hypergraph associated with the data matrix and a graph coarsening strategy based on column matching. We consider a number of standard applications of this technique as well as a few new ones. Among standard applications, we first consider the problem of computing partial singular value decomposition, for which a combination of sampling and coarsening yields significantly improved singular value decomposition results relative to sampling alone. We also consider the column subset selection problem, a popular low‐rank approximation method used in data‐related applications, and show how multilevel coarsening can be adapted for this problem. Similarly, we consider the problem of graph sparsification and show how coarsening techniques can be employed to solve it. We also establish theoretical results that characterize the approximation error obtained and the quality of the dimension reduction achieved by a coarsening step, when a proper column matching strategy is employed. Numerical experiments illustrate the performances of the methods in a few applications.     

Vibrations of a semicircular membrane containing thin rigid inclusions

This article examines problems concerning steady-state vibrations of a semicircular membrane containing thin rigid inclusions of different configurations. The generalized method of integral transforms is used to formulate the problem in the form of a system of singular integral equations in each specific case. With the use of the asymptote of the sought functions as a basis, these equations are solved approximately by the method of orthogonal polynomials. A study is made of the validity of using the reduction method to approximately solve the infinite linear algebraic matrix system which is obtained. The results of calculations are analyzed.Translated from Dinamicheskie Sistemy, No. 5, pp. 49–55, 1986.