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.     

Computing the optimal commuting matrix pairs

A matrix can be modified by an additive perturbation so that it commutes with any given matrix. In this paper, we discuss several algorithms for computing the smallest perturbation in the Frobenius norm for a given matrix pair. The algorithms have applications in 2-D direction-of-arrival finding in array signal processing. The work of first author was supported in part by NSF grant CCR-9308399. The work of the second author was supported in part by China State Major Key Project for Basic Researches.     

Modifying the generalized singular value decomposition with application with application in direction-of-arrival finding

We consider updating and downdating problems for the generalized singular value decomposition (GSVD) of matrix pairs when new rows are added to one of the matrices or old rows are deleted. Two classes of algorithms are developed, one based on the CS decomposition formulation of the GSVD and the other based on the generalized eigenvalue decomposition formulation. In both cases we show that the updating and downdating problems can be reduced to a rank-one SVD updating problem. We also provide perturbation analysis for the cases when the added or deleted rows are subject to errors. Numerical experiments on direction-of-arrival (DOA) finding with colored noises are carried out to demonstrate the tracking ability of the algorithms. The work of the first author was supported in part by NSF grants CCR-9308399 and CCR-9619452. The work of the second author was supported in part by China State Major Key Project for Basic Researches.     

On point covers of multiple intervals and axis-parallel rectangles

In certain families of hypergraphs the transversal number is bounded by some function of the packing number. In this paper we study hypergraphs related to multiple intervals and axisparallel rectangles, respectively. Essential improvements of former established upper bounds are presented here. We explore the close connection between the two problems at issue.Supported by the Alexander von Humboldt Foundation and the NSF grant No. STC-91-19999Supported by the NSF grant No. CCR-92-00788, the (Hungarian) National Scientific Research Fund (OTKA) grant No. F014919. The author was visiting the Computation and Automation Institute, Budapest while part of this research was done.     

Backward stability of a pivoting strategy for sign-regular linear systems

A matrixA issign-regular if, for each orderk, allk×k submatrices ofA have determinant with the same sign. In this paper, a pivoting strategy ofO(n) operations for the Gaussian elimination of linear systems whose coefficient matrices are sign-regular is proposed. Backward error analysis of this pivoting strategy is performed and small error bounds are obtained. Our results can also be applied to linear systems whose coefficient matrices have sign-regular inverses.     

Symmetric Gaussian elimination for cauchy-type matrices with application to positive definite Toeplitz matrices

The problem of solving linear equations with a Toeplitz matrix appears in many applications. Often is positive definite but ill-conditioned with many small eigenvalues. In this case fast and superfast algorithms may show a very poor behavior or even break down. In recent papers the transformation of a Toeplitz matrix into a Cauchy-type matrix is proposed. The resulting new linear equations can be solved in operations using standard pivoting strategies which leads to very stable fast methods also for ill-conditioned systems. The basic tool is the formulation of Gaussian elimination for matrices with low displacement rank. In this paper, we will transform a Hermitian Toeplitz matrix into a Cauchy-type matrix by applying the Fourier transform. We will prove some useful properties of and formulate a symmetric Gaussian elimination algorithm for positive definite . Using the symmetry and persymmetry of we can reduce the total costs of this algorithm compared with unsymmetric Gaussian elimination. For complex Hermitian , the complexity of the new algorithm is then nearly the same as for the Schur algorithm. Furthermore, it is possible to include some strategies for ill-conditioned positive definite matrices that are well-known in optimization. Numerical examples show that this new algorithm is fast and reliable. Received March 24, 1995 / Revised version received December 13, 1995     

Performance Study and Analysis of Parallel Multilevel Preconditioners

The significant gap between peak and realized performance of parallel systems motivates the need for performance analysis. In order to predict the performance of a class of parallel multilevel ILU preconditioner (PBILUM), we build two performance prediction models for both the preconditioner construction phase and the solution phase. These models combine theoretical features of the preconditioners with estimates on computation cost, communications overhead, etc. Experimental simulations show that our model predication based on certain reasonable assumptions is close to the simulation results. The models may be used to predict the performance of this class of parallel preconditioners.*The research work of the authors was supported in part by the U.S. National Science Foundation under grants CCR-9988165, CCR-0092532, ACR-0202934, and ACR-234270, by the U.S. Department of Energy Office of Science under grant DE-FG02-02ER45961, by the Kentucky Science & Engineering Foundation under grant KSEF-02-264-RED-002.     

Sparse null basis computations in structural optimization

Summary We study the computation of sparse null bases of equilibrium matrices in the context of the force method in structural optimization. Two classes of structural problems are considered. For the class of rigid jointed skeletal structures, we use a partitioning method suggested by Henderson and Maunder to partition the problem into a set of independent null basis computations. For the class of structures represented by a continuum, we compute a sizable fraction of the null vectors in a basis from a consideration of the finite element formulation and the bipartite graph of the equilibrium matrix. The remaining null vectors are computed by the triangular algorithm in [6]. The new algorithms find sparser bases than the triangular algorithm and are also faster.This research was partially supported by NSF grant CCR-8701723 and AFOSR grant 88-0161     

Component-wise perturbation analysis and error bounds for linear least squares solutions

Perturbation bounds for the linear least squares problem min _x Ax –b₂ corresponding tocomponent-wise perturbations in the data are derived. These bounds can be computed using a method of Hager and are often much better than the bounds derived from the standard perturbation analysis. In particular this is true for problems where the rows ofA are of widely different magnitudes. Generalizing a result by Oettli and Prager, we can use the bounds to compute a posteriori error bounds for computed least squares solutions.     

A note on matrices with maximal growth factor for Neville elimination

Neville elimination is a direct method for the solution of linear systems of equations with advantages for some classes of matrices and in the context of pivoting strategies for parallel implementations. The growth factor is an indicator of the numerical stability of an algorithm. In the literature, bounds for the growth factor of Neville elimination with some pivoting strategies have appeared. In this work, we determine all the matrices such that the minimal upper bound of the growth factor of Neville elimination with those pivoting strategies is reached.     

Path problems in skew-symmetric graphs

We study path problems in skew-symmetric graphs. These problems generalize the standard graph reachability and shortest path problems. We establish combinatorial solvability criteria and duality relations for the skew-symmetric path problems and use them to design efficient algorithms for these problems. The algorithms presented are competitive with the fastest algorithms for the standard problems.This research was done while the first author was at Stanford University Computer Science Department, supported in part by ONR Office of Naval Research Young Investigator Award N00014-91-J-1855, NSF Presidential Young Investigator Grant CCR-8858097 with matching funds from AT&T, DEC, and 3M, and a grant from Powell Foundation.This research was done while the second author was visiting Stanford University Computer Science Department and supported by the above mentioned NSF and Powell Foundation Grants.     

Perturbation theory and backward error forAX−XB=C

Because of the special structure of the equationsAX–XB=C the usual relation for linear equations backward error = relative residual does not hold, and application of the standard perturbation result forAx=b yields a perturbation bound involving sep (A, B)^–1 that is not always attainable. An expression is derived for the backward error of an approximate solutionY; it shows that the backward error can exceed the relative residual by an arbitrary factor. A sharp perturbation bound is derived and it is shown that the condition number it defines can be arbitrarily smaller than the sep(A, B)^–1-based quantity that is usually used to measure sensitivity. For practical error estimation using the residual of a computed solution an LAPACK-style bound is shown to be efficiently computable and potentially much smaller than a sep-based bound. A Fortran 77 code has been written that solves the Sylvester equation and computes this bound, making use of LAPACK routines.Nuffield Science Research Fellow. This work was carried out while the author was a visitor at the Institute for Mathematics and its Applications, University of Minnesota.     

On a direct method for the solution of nearly uncoupled Markov chains

Summary This note is concerned with the accuracy of the solution of nearly uncoupled Markov chains by a direct method based on the LU decomposition. It is shown that plain Gaussian elimination may fail in the presence of rounding errors. A modification of Gaussian elimination with diagonal pivoting and correction of small pivots is proposed and analyzed. It is shown that the accuracy of the solution is affected by two condition numbers associated with aggregation and the coupling respectively.This work was supported in part by the Air Force Office of Sponsored Research under Contract AFOSR-87-0188     

Componentwise error analysis for the block LU factorization of totally nonnegative matrices

For the first time, perturbation bounds including componentwise perturbation bounds for the block LU factorization have been provided by Dopico and Molera (2005) [5]. In this paper, componentwise error analysis is presented for computing the block LU factorization of nonsingular totally nonnegative matrices. We present a componentwise bound on the equivalent perturbation for the computed block LU factorization. Consequently, combining with the componentwise perturbation results we derive componentwise forward error bounds for the computed block factors.     

Error analysis of the Björck-Pereyra algorithms for solving Vandermonde systems

Summary A forward error analysis is presented for the Björck-Pereyra algorithms used for solving Vandermonde systems of equations. This analysis applies to the case where the points defining the Vandermonde matrix are nonnegative and are arranged in increasing order. It is shown that for a particular class of Vandermonde problems the error bound obtained depends on the dimensionn and on the machine precision only, being independent of the condition number of the coefficient matrix. By comparing appropriate condition numbers for the Vandermonde problem with the forward error bounds it is shown that the Björck-Pereyra algorithms introduce no more uncertainty into the numerical solution than is caused simply by storing the right-hand side vector on the computer. A technique for computing running a posteriori error bounds is derived. Several numerical experiments are presented, and it is observed that the ordering of the points can greatly affect the solution accuracy.     

Growth factor and expected growth factor of some pivoting strategies

Several definitions of growth factors for Gaussian elimination are compared. Some new pivoting strategies, intermediate between partial pivoting and rook pivoting, are introduced. For random matrices, an approximation of the average normalized growth factor associated with several pivoting strategies is computed and analyzed. A stationary behavior of the expected growth factors of the new pivoting strategies is observed. Bounds for the growth factors of these pivoting strategies are provided. It is also shown that partial pivoting by columns produces small growth factors for matrices appearing in practical observations and for which the growth factors produced by partial pivoting are very large.     

Relaxed and stabilized incomplete factorizations for non-self-adjoint linear systems

Two classes of incomplete factorization preconditioners are considered for nonsymmetric linear systems arising from second order finite difference discretizations of non-self-adjoint elliptic partial differential equations. Analytic and experimental results show that relaxed incomplete factorization methods exhibit numerical instabilities of the type observed with other incomplete factorizations, and the effects of instability are characterized in terms of the relaxation parameter. Several stabilized incomplete factorizations are introduced that are designed to avoid numerically unstable computations. In experiments with two-dimensional problems with variable coefficients and on nonuniform meshes, the stabilized methods are shown to be much more robust than standard incomplete factorizations.The work presented in this paper was supported by the National Science Foundation under grants DMS-8607478, CCR-8818340, and ASC-8958544, and by the U.S. Army Research Office under grant DAAL-0389-K-0016.     

Optimal convex hull algorithms on enhanced meshes

In this paper we propose time-optimal convex hull algorithms for two classes of enhanced meshes. Our first algorithm computes the convex hull of an arbitrary set ofn points in the plane inO (logn) time on a mesh with multiple broadcasting of sizen×n. The second algorithm shows that the same problem can be solved inO (1) time on a reconfigurable mesh of sizen×n. Both algorithms achieve time lower bounds for their respective model of computation.This work was supported by NASA under grant NCCI-99.Additional support by the National Science Foundation under grant CCR-8909996 is gratefully acknowledged.     

Pivoting strategies leading to diagonal dominance by rows

Pivoting strategies for Gaussian elimination leading to upper triangular matrices which are diagonally dominant by rows are studied. Forward error analysis of triangular systems whose coefficient matrices are diagonally dominant by rows is performed. We also obtain small bounds of the backward errors for the pivoting strategies mentioned above. Our examples of matrices include H-matrices and some generalizations of diagonally dominant matrices, and scaled partial pivoting for the 1-norm is an example of these pivoting strategies. In the case of an M-matrix, a pivoting strategy of computational complexity is proposed, which satisfies all the results of the paper. Received June 6, 1997 / Revised version received October 27, 1997     

Perturbation analysis of generalized saddle point systems

We discuss the perturbation analysis of generalized saddle point systems in this paper. We give the nonlinear perturbation bounds, then derive the condition numbers, and analyze the sensitivity of the computed solutions.