A generalized successive overrelaxation method for least squares problems

In this paper a new iterative method is given for solving large sparse least squares problems and computing the minimum norm solution to underdetermined consistent linear systems. The new scheme is called the generalized successive overrelaxation (GSOR) method and is shown to be convergent ifA is full column rank. The GSOR method involves a parameter ρ and an auxiliary matrixP. One can choose matrix P so that the GSOR method only involves matrix and vector operations; therefore the GSOR method is suitable for parallel computations. Besides, the GSOR method can be combined with preconditioning techniques, and therefore can be expected to be more effective. This author's work was supported by Natural Science Foundation of Liaoning Province, China.     

Estimating the largest singular values of large sparse matrices via modified moments

We describe a procedure for determining a few of the largest singular values of a large sparse matrix. The method by Golub and Kent which uses the method of modified moments for estimating the eigenvalues of operators used in iterative methods for the solution of linear systems of equations is appropriately modified in order to generate a sequence of bidiagonal matrices whose singular values approximate those of the original sparse matrix. A simple Lanczos recursion is proposed for determining the corresponding left and right singular vectors. The potential asynchronous computation of the bidiagonal matrices using modified moments with the iterations of an adapted Chebyshev semi-iterative (CSI) method is an attractive feature for parallel computers. Comparisons in efficiency and accuracy with an appropriate Lanczos algorithm (with selective re-orthogonalization) are presented on large sparse (rectangular) matrices arising from applications such as information retrieval and seismic reflection tomography. This procedure is essentially motivated by the theory of moments and Gauss quadrature.This author's work was supported by the National Science Foundation under grants NSF CCR-8717492 and CCR-910000N (NCSA), the U.S. Department of Energy under grant DOE DE-FG02-85ER25001, and the Air Force Office of Scientific Research under grant AFOSR-90-0044 while at the University of Illinois at Urbana-Champaign Center for Supercomputing Research and Development.This author's work was supported by the U.S. Army Research Office under grant DAAL03-90-G-0105, and the National Science Foundation under grant NSF DCR-8412314.     

Solving sparse linear systems by an abs-method that corresponds toLU-decomposition

Abaffy, Broyden, and Spedicato (ABS) have recently proposed a class of direct methods for solving nonsparse linear systems. It is the purpose of this paper to demonstrate that with proper choice of parameters, ABS methods exploit sparsity in a natural way. In particular, we study the choice of parameters which corresponds to an LU-decomposition of the coefficient matrix. In many cases, the fill-in, represented by the nonzero elements of the deflection matrix, uses less storage than the corresponding fill-in of an explicit LU factorization. Hence the above can be a viable and simple method for solving sparse linear systems. A simple reordering scheme for the coefficient matrix is also proposed for the purpose of reducing fill-in of the deflection matrices.     

Using FFT-based techniques in polynomial and matrix computations: recent advances and applicatons

Computations with univariate polynomials, like the evaluation of product, quotient, remainder, greatest common divisor, etc, are closely related to linear algebra computations performed with structured matrices having the Toeplitz-like or the Hankel-like structures.

The discrete Fourier transform, and the FFT algorithms for its computation, constitute a powerful tool for the design and analysis of fast algorithms for solving problems involving polynomials and structured matrices.

We recall the main correlations between polynomial and matrix computations and present two recent results in this field: in particular, we show how Fourier methods can speed up the solution of a wide class of problems arising in queueing theory where certain Markov chains, defined by infinite block Toeplitz matrices in generalized Hessenberg form, must be solved. Moreover, we present a new method for the numerical factorization of polynomials based on a matrix generalization of Koenig's theorem. This method, that relies on the evaluation/interpolation technique at the Fourier points, reduces the problem of polynomial factorization to the computation of the LU decomposition of a banded Toeplitz matrix with its rows and columns suitably permuted. Numerical experiments that show the effectiveness of our algorithms are presented     

Matrix computations and polynomial root-finding with preprocessing

Solution of homogeneous linear systems of equations is a basic operation of matrix computations. The customary algorithms rely on pivoting, orthogonalization and SVD, but we employ randomized preprocessing instead. This enables us to accelerate the solution dramatically, both in terms of the estimated arithmetic cost and the observed CPU time. The approach is effective in the cases of both general and structured input matrices and we extend it and its computational advantages to the solution of nonhomogeneous linear systems of equations, matrix eigen-solving, the solution of polynomial and secular equations, and approximation of a matrix by a nearby matrix that has a smaller rank or a fixed structure (e.g., of the Toeplitz or Hankel type). Our analysis and extensive experiments show the power of the presented algorithms.     

Preconditioned iterative methods for a class of nonlinear eigenvalue problems

This paper proposes new iterative methods for the efficient computation of the smallest eigenvalue of symmetric nonlinear matrix eigenvalue problems of large order with a monotone dependence on the spectral parameter. Monotone nonlinear eigenvalue problems for differential equations have important applications in mechanics and physics. The discretization of these eigenvalue problems leads to nonlinear eigenvalue problems with very large sparse ill-conditioned matrices monotonically depending on the spectral parameter. To compute the smallest eigenvalue of large-scale matrix nonlinear eigenvalue problems, we suggest preconditioned iterative methods: preconditioned simple iteration method, preconditioned steepest descent method, and preconditioned conjugate gradient method. These methods use only matrix-vector multiplications, preconditioner-vector multiplications, linear operations with vectors, and inner products of vectors. We investigate the convergence and derive grid-independent error estimates for these methods. Numerical experiments demonstrate the practical effectiveness of the proposed methods for a model problem.     

Sparse approximate inverse preconditioning for dense linear systems arising in computational electromagnetics

We investigate the use of sparse approximate inverse preconditioners for the iterative solution of linear systems with dense complex coefficient matrices arising in industrial electromagnetic problems. An approximate inverse is computed via a Frobenius norm approach with a prescribed nonzero pattern. Some strategies for determining the nonzero pattern of an approximate inverse are described. The results of numerical experiments suggest that sparse approximate inverse preconditioning is a viable approach for the solution of large-scale dense linear systems on parallel computers. This revised version was published online in August 2006 with corrections to the Cover Date.     

On the modification of an eigenvalue problem that preserves an eigenspace

Eigenvalue problems arise in many application areas ranging from computational fluid dynamics to information retrieval. In these fields we are often interested in only a few eigenvalues and corresponding eigenvectors of a sparse matrix. In this paper, we comment on the modifications of the eigenvalue problem that can simplify the computation of those eigenpairs. These transformations allow us to avoid difficulties associated with non-Hermitian eigenvalue problems, such as the lack of reliable non-Hermitian eigenvalue solvers, by mapping them into generalized Hermitian eigenvalue problems. Also, they allow us to expose and explore parallelism. They require knowledge of a selected eigenvalue and preserve its eigenspace. The positive definiteness of the Hermitian part is inherited by the matrices in the generalized Hermitian eigenvalue problem. The position of the selected eigenspace in the ordering of the eigenvalues is also preserved under certain conditions. The effect of using approximate eigenvalues in the transformation is analyzed and numerical experiments are presented.     

A tearing-based hybrid parallel sparse linear system solver

We propose a hybrid sparse system solver for handling linear systems using algebraic domain decomposition-based techniques. The solver consists of several stages. The first stage uses a reordering scheme that brings as many of the largest matrix elements as possible closest to the main diagonal. This is followed by partitioning the coefficient matrix into a set of overlapped diagonal blocks that contain most of the largest elements of the coefficient matrix. The only constraint here is to minimize the size of each overlap. Separating these blocks into independent linear systems with the constraint of matching the solution parts of neighboring blocks that correspond to the overlaps, we obtain a balance system. This balance system is not formed explicitly and has a size that is much smaller than the original system. Our novel solver requires only a one-time factorization of each diagonal block, and in each outer iteration, obtaining only the upper and lower tips of a solution vector where the size of each tip is equal to that of the individual overlap. This scheme proves to be scalable on clusters of nodes in which each node has a multicore architecture. Numerical experiments comparing the scalability of our solver with direct and preconditioned iterative methods are also presented.     

On nonsingularity of block two-by-two matrices

We derive necessary and sufficient conditions for guaranteeing the nonsingularity of a block two-by-two matrix by making use of the singular value decompositions and the Moore–Penrose pseudoinverses of the matrix blocks. These conditions are complete, and much weaker and simpler than those given by Decker and Keller [D.W. Decker, H.B. Keller, Multiple limit point bifurcation, J. Math. Anal. Appl. 75 (1980) 417–430], and may be more easily examined than those given by Bai [Z.-Z. Bai, Eigenvalue estimates for saddle point matrices of Hermitian and indefinite leading blocks, J. Comput. Appl. Math. 237 (2013) 295–306] from the computational viewpoint. We also derive general formulas for the rank of the block two-by-two matrix by utilizing either the unitarily compressed or the orthogonally projected sub-matrices.     

Saving flops in LU based shift-and-invert strategy

The shift-and-invert method is very efficient in eigenvalue computations, in particular when interior eigenvalues are sought. This method involves solving linear systems of the form (A−σI)z=b. The shift σ is variable, hence when a direct method is used to solve the linear system, the LU factorization of (A−σI) needs to be computed for every shift change. We present two strategies that reduce the number of floating point operations performed in the LU factorization when the shift changes. Both methods perform first a preprocessing step that aims at eliminating parts of the matrix that are not affected by the diagonal change. This leads to about 43% and 50% flops savings respectively for the dense matrices.     

Implementación eficiente de una formulación semirrecursiva para la dinámica de sistemas multicuerpo de gran tamaño

This article shows an efficient implementation of a dynamic semi-recursive formulation for large and complex multibody system simulations, with interesting applications in the automotive field and especially with industrial vehicles. These systems tend to have a huge amount of kinematic constraints, becoming usual the presence of redundant but compatible systems of equations. The maths involved in the solution of these problems have a high computational cost, making very challenging to achieve real-time simulations.In this article, two implementations to increase the efficiency of these computations will be shown. The difference between them is the way they consider the Jacobian matrix of the constraint equations. The first one treats this matrix as a dense one, using the BLAS functions to solve the system of equations. The second one takes into account the sparse pattern of the Jacobian matrix, introducing the sparse function MA48 from Harwell.Both methodologies have been applied on two multibody system models with different sizes. The first model is a vehicle IVECO DAILY 35C15 with 17 degrees of freedom. The second one is a semi-trailer truck with 40 degrees of freedom. Taking as a reference the standard C/C + + implementation, the efficiency improvements that have been achieved using dense matrices (BLAS) have been of 15% and 50% respectively. The results in the first model have not improved significantly by using sparse matrices, but in the second one, the times with sparse matrices have been reduced 8% with respect to the BLAS ones.     

On CSCS-based iteration methods for Toeplitz system of weakly nonlinear equations

For Toeplitz system of weakly nonlinear equations, by using the separability and strong dominance between the linear and the nonlinear terms and using the circulant and skew-circulant splitting (CSCS) iteration technique, we establish two nonlinear composite iteration schemes, called Picard-CSCS and nonlinear CSCS-like iteration methods, respectively. The advantage of these methods is that they do not require accurate computation and storage of Jacobian matrix, and only need to solve linear sub-systems of constant coefficient matrices. Therefore, computational workloads and computer storage may be saved in actual implementations. Theoretical analysis shows that these new iteration methods are local convergent under suitable conditions. Numerical results show that both Picard-CSCS and nonlinear CSCS-like iteration methods are feasible and effective for some cases.     

Additive preconditioning for matrix computations

Our randomized additive preconditioners are readily available and regularly facilitate the solution of linear systems of equations and eigen-solving for a very large class of input matrices. We study the generation of such preconditioners and their impact on the rank and the condition number of a matrix. We also propose some techniques for their refinement and two alternative versions of randomized preprocessing. Our analysis and experiments show the power of our approach even where we employ weak randomization, that is generate sparse and structured preconditioners, defined by a small number of random parameters.     

The {\cal {D Q R}} algorithm, basic theory, convergence, and conditional stability

Summary. We describe a fast matrix eigenvalue algorithm that uses a matrix factorization and reverse order multiply technique involving three factors and that is based on the symmetric matrix factorization as well as on –orthogonal reduction techniques where is computed from the given matrix . It operates on a similarity reduction of a real matrix to general tridiagonal form and computes all of 's eigenvalues in operations, where the part of the operations is possibly performed over , instead of the 7–8 real flops required by the eigenvalue algorithm. Potential breakdo wn of the algorithm can occur in the reduction to tridiagonal form and in the –orthogonal reductions. Both, however, can be monitored during the computations. The former occurs rather rarely for dimensions and can essentially be bypassed, while the latter is extremely rare and can be bypassed as well in our conditionally stable implementation of the steps. We prove an implicit theorem which allows implicit shifts, give a convergence proof for the algorithm and show that is conditionally stable for general balanced tridiagonal matrices . Received April 25, 1995 / Revised version received February 9, 1996     

Data structures to vectorize CG algorithms for general sparsity patterns

We describe an implementation of Conjugate Gradient-type iterative algorithms for problems with general sparsity patterns on a vector processor with a hierarchy of memories, such as the IBM 3090/VF. The implementation relies on the wavefront approach to vectorize the solution of the two sparse triangular systems that arise when using ILU type preconditioners. The data structure is the key to an effective implementation of sparse computational kernels on a vector processor. A data structure is a combination of a layout of the matrix coefficients and ordering schemes for the vectors to increase data locality. With the data structure we describe, we achieve comparable performance on both the matrix-vector product and the solution of the sparse triangular systems on a variety of real problems, such as those arising from large scale reservoir simulation or structural analysis.     

Approximate iterations for structured matrices

Important matrix-valued functions f (A) are, e.g., the inverse A ⁻¹, the square root and the sign function. Their evaluation for large matrices arising from pdes is not an easy task and needs techniques exploiting appropriate structures of the matrices A and f (A) (often f (A) possesses this structure only approximately). However, intermediate matrices arising during the evaluation may lose the structure of the initial matrix. This would make the computations inefficient and even infeasible. However, the main result of this paper is that an iterative fixed-point like process for the evaluation of f (A) can be transformed, under certain general assumptions, into another process which preserves the convergence rate and benefits from the underlying structure. It is shown how this result applies to matrices in a tensor format with a bounded tensor rank and to the structure of the hierarchical matrix technique. We demonstrate our results by verifying all requirements in the case of the iterative computation of A ⁻¹ and . This work was performed during the stay of the third author at the Max-Planck-Institute for Mathematics in the Sciences (Leipzig) and also supported by the Russian Fund of Basic Research (grants 05-01-00721, 04-07-90336) and a Priority Research Grant of the Department of Mathematical Sciences of the Russian Academy of Sciences.     

Hyman’s method revisited

The QR algorithm is considered one of the most reliable methods for computing matrix eigenpairs. However, it is unable to detect multiple eigenvalues and Jordan blocks. Matlab’s eigensolver returns heavily perturbed eigenvalues and eigenvectors in such cases and there is no hint for possible principal vectors. This paper calls attention to Hyman’s method as it is applicable for computing principal vectors and higher derivatives of the characteristic polynomial that may help to estimate multiplicity, an important information for more reliable computation. We suggest a test matrix collection for Jordan blocks. The first numerical tests with these matrices reveal that the computational problems are deeper than expected at the beginning of this work.     

A Frisch-Newton Algorithm for Sparse Quantile Regression

Recent experience has shown that interior-point methods using a log barrier approach are far superior to classical simplex methods for computing solutions to large parametric quantile regression problems. In many large empirical applications, the design matrix has a very sparse structure. A typical example is the classical fixed-effect model for panel data where the parametric dimension of the model can be quite large, but the number of non-zero elements is quite small. Adopting recent developments in sparse linear algebra we introduce a modified version of the Prisch-Newton algorithm for quantile regression described in Portnoy and Koenker~([28]). The new algorithm substantially reduces the storage (memory) requirements and increases computational speed. The modified algorithm also facilitates the development of nonparametric quantile regression methods. The pseudo design matrices employed in nonparametric quantile regression smoothing are inherently sparse in both the fidelity and roughness penalty components. Exploiting the sparse structure of these problems opens up a whole range of new possibilities for multivariate smoothing on large data sets via ANOVA-type decomposition and partial linear models.