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.     

Numerical Properties of Shifted Tridiagonal LU Factorizations

In this paper, we consider shifted tridiagonal matrices. We prove that the standard algorithm to compute the LU factorization in this situation is mixed forward-backward stable and, therefore, componentwise forward stable. Moreover, we give a formula to compute the corresponding condition number in O(n) flops. This research has been partially supported by Dirección General de Investigación (Ministerio de Ciencia y Tecnología) of Spain through grants BFM2003-06335-C03-02 and MTM2006-06671 as well as by the Postdoctoral Fellowship EX2004-0658 provided by Ministerio de Educación y Ciencia of Spain.     

The structured sensitivity of Vandermonde-like systems

Summary We consider a general class of structured matrices that includes (possibly confluent) Vandermonde and Vandermonde-like matrices. Here the entries in the matrix depend nonlinearly upon a vector of parameters. We define, condition numbers that measure the componentwise sensitivity of the associated primal and dual solutions to small componentwise perturbations in the parameters and in the right-hand side. Convenient expressions are derived for the infinity norm based condition numbers, and order-of-magnitude estimates are given for condition numbers defined in terms of a general vector norm. We then discuss the computation of the corresponding backward errors. After linearising the constraints, we derive an exact expression for the infinity norm dual backward error and show that the corresponding primal backward error is given by the minimum infinity-norm solution of an underdetermined linear system. Exact componentwise condition numbers are also derived for matrix inversion and the least squares problem, and the linearised least squares backward error is characterised.     

On mixed and componentwise condition numbers for Moore-Penrose inverse and linear least squares problems

Classical condition numbers are normwise: they measure the size of both input perturbations and output errors using some norms. To take into account the relative of each data component, and, in particular, a possible data sparseness, componentwise condition numbers have been increasingly considered. These are mostly of two kinds: mixed and componentwise. In this paper, we give explicit expressions, computable from the data, for the mixed and componentwise condition numbers for the computation of the Moore-Penrose inverse as well as for the computation of solutions and residues of linear least squares problems. In both cases the data matrices have full column (row) rank.

     

Accurate solutions of diagonally dominant tridiagonal linear systems

In this paper, we settle Higham’s conjecture for the LU factorization of diagonally dominant tridiagonal matrices. We establish a strong componentwise perturbation bound for the solution of a diagonally dominant tridiagonal linear system, independent of the traditional condition number of the coefficient matrix. We then accurately and efficiently solve the linear system by the GTH-like algorithm without pivoting, as suggested by the perturbation result.     

On the row merge tree for sparse LU factorization with partial pivoting

We consider the problem of structure prediction for sparse LU factorization with partial pivoting. In this context, it is well known that the column elimination tree plays an important role for matrices satisfying an irreducibility condition, called the strong Hall property. Our primary goal in this paper is to address the structure prediction problem for matrices satisfying a weaker assumption, which is the Hall property. For this we consider the row merge matrix, an upper bound that contains the nonzeros in L and U for all possible row permutations that can be performed during the numerical factorization with partial pivoting. We discuss the row merge tree, a structure that represents information obtained from the row merge matrix; that is, information on the dependencies among the columns in Gaussian elimination with partial pivoting and on structural upper bounds of the factors L and U. We present new theoretical results that show that the nonzero structure of the row merge matrix can be described in terms of branches and subtrees of the row merge tree. These results lead to an efficient algorithm for the computation of the row merge tree, that uses as input the structure of A, and has a time complexity almost linear in the number of nonzeros in A. We also investigate experimentally the usage of the row merge tree for structure prediction purposes on a set of matrices that satisfy only the Hall property. We analyze in particular the size of upper bounds of the structure of L and U, the reordering of the matrix based on a postorder traversal and its impact on the factorization runtime. We show experimentally that for some matrices, the row merge tree is a preferred alternative to the column elimination tree. AMS subject classification (2000)  65F50, 65F05, 68R10     

On the stability of the cyclic reduction without back substitution for tridiagonal systems

Componentwise error analysis for a modification of the cyclic reduction without back substitution for a tridiagonal system is presented. We consider relative roundoff errors and equivalent perturbations, so the main supposition is that all the data is nonzero. First, backward analysis for the computation of each component of the solution in separate is presented. Bounds on the relative equivalent perturbations are obtained depending on two constants. From these bounds it is easy to obtain a componentwise forward error analysis. Then the two constants are defined for some special classes of matrices, i.e. diagonally dominant (row or column), symmetric positive definite, totally nonnegative andM-matrices, and it is shown that the bounds for these classes of matrices are small.The author was supported by Grants MM-211/92 and MM-434/94 from the National Scientific Research Fund of the Bulgarian Ministry of Education and Science.     

Densities of One-Dimensional Backward SDEs

This work is devoted to the study of the existence and smoothness of the marginal densities of the solution of one-dimensional backward stochastic differential equations. Under monotonicity conditions of a function of the coefficients, we obtain that the smoothness properties of the forward process influencing the backward equation, transfer to the densities of the solution. Once established these conditions, we apply the result to study the tail behavior of the solution process. Mathematics Subject Classification (2000) 60H10.Fabio Antonelli: The first author was partially supported by the MIUR COFIN grant 2000.Arturo Kohatsu-Higa: The second author was partially supported by grants BFM2003-03324 and BFM 2003-04294. The authors wish to thank the referee for his/her comments.     

Forward error analysis of Gaussian elimination

Summary Part I of this work deals with the forward error analysis of Gaussian elimination for general linear algebraic systems. The error analysis is based on a linearization method which determines first order approximations of the absolute errors exactly. Superposition and cancellation of error effects, structure and sparsity of the coefficient matrices are completely taken into account by this method. The most important results of the paper are new condition numbers and associated optimal component-wise error and residual estimates for the solutions of linear algebraic systems under data perturbations and perturbations by rounding erros in the arithmetic floating-point operations. The estimates do not use vector or matrix norms. The relative data and rounding condition numbers as well as the associated backward and residual stability constants are scaling-invariant. The condition numbers can be computed approximately from the input data, the intermediate results, and the solution of the linear system. Numerical examples show that by these means realistic bounds of the errors and the residuals of approximate solutions can be obtained. Using the forward error analysis, also typical results of backward error analysis are deduced. Stability theorems and a priori error estimates for special classes of linear systems are proved in Part II of this work.     

Block LU factorizations of M–matrices

Summary. It is well known that any nonsingular M–matrix admits an LU factorization into M–matrices (with L and U lower and upper triangular respectively) and any singular M–matrix is permutation similar to an M–matrix which admits an LU factorization into M–matrices. Varga and Cai establish necessary and sufficient conditions for a singular M–matrix (without permutation) to allow an LU factorization with L nonsingular. We generalize these results in two directions. First, we find necessary and sufficient conditions for the existence of an LU factorization of a singular M-matrix where L and U are both permitted to be singular. Second, we establish the minimal block structure that a block LU factorization of a singular M–matrix can have when L and U are M–matrices. Received November 21, 1994 / Revised version received August 4, 1997     

Indefinite QR Factorization

Let A be a Hermitian positive definite matrix given by its rectangular factor G such that A=G^*G. It is well known that the Cholesky factorization of A is equivalent to the QR factorization of G. In this paper, an analogue of the QR factorization for Hermitian indefinite matrices is constructed. This problem has been considered by many authors, but the problem of zero diagonal elements has not been solved so far. Here we show how to overcome this difficulty. AMS subject classification (2000) 65F25, 46C20, 65F15     

A New Approach to Backward Error Analysis of Lu Factorization

A new backward error analysis of LU factorization is presented. It allows to obtain a sharper upper bound for the forward error and a new definition of the growth factor that we compare with the well known Wilkinson growth factor for some classes of matrices. Numerical experiments show that the new growth factor is often of order approximately log₂ n whereas Wilkinson's growth factor is of order n or .     

Iterative refinement enhances the stability ofQR factorization methods for solving linear equations

Iterative refinement is a well-known technique for improving the quality of an approximate solution to a linear system. In the traditional usage residuals are computed in extended precision, but more recent work has shown that fixed precision is sufficient to yield benefits for stability. We extend existing results to show that fixed precision iterative refinement renders anarbitrary linear equations solver backward stable in a strong, componentwise sense, under suitable assumptions. Two particular applications involving theQR factorization are discussed in detail: solution of square linear systems and solution of least squares problems. In the former case we show that one step of iterative refinement suffices to produce a small componentwise relative backward error. Our results are weaker for the least squares problem, but again we find that iterative refinement improves a componentwise measure of backward stability. In particular, iterative refinement mitigates the effect of poor row scaling of the coefficient matrix, and so provides an alternative to the use of row interchanges in the HouseholderQR factorization. A further application of the results is described to fast methods for solving Vandermonde-like systems.     

A Class of Incomplete Orthogonal Factorization Methods. II: Implementation and Results

We present, implement and test several incomplete QR factorization methods based on Givens rotations for sparse square and rectangular matrices. For square systems, the approximate QR factors are used as right-preconditioners for GMRES, and their performance is compared to standard ILU techniques. For rectangular matrices corresponding to linear least-squares problems, the approximate R factor is used as a right-preconditioner for CGLS. A comprehensive discussion is given about the uses, advantages and shortcomings of the preconditioners. AMS subject classification (2000) 65F10, 65F25, 65F50.Received May 2002. Revised October 2004. Communicated by Åke Björck.     

Using dual techniques to derive componentwise and mixed condition numbers for a linear function of a linear least squares solution

We prove duality results for adjoint operators and product norms in the framework of Euclidean spaces. We show how these results can be used to derive condition numbers especially when perturbations on data are measured componentwise relatively to the original data. We apply this technique to obtain formulas for componentwise and mixed condition numbers for a linear function of a linear least squares solution. These expressions are closed when perturbations of the solution are measured using a componentwise norm or the infinity norm and we get an upper bound for the Euclidean norm.      

On the sensitivity of the LU factorization

This paper gives sensitivity analyses by two approaches forL andU in the factorizationA=LU for general perturbations inA which are sufficiently small in norm. By the matrix-vector equation approach, we derive the condition numbers for theL andU factors. By the matrix equation approach we derive corresponding condition estimates. We show how partial pivoting and complete pivoting affect the sensitivity of the LU factorization. The material presented here is a part of the first author's PhD thesis under the supervision of the second author. This research was supported by NSERC of Canada Grant OGP0009236.     

Perturbation analysis and condition numbers of scaled total least squares problems

The standard approaches to solving an overdetermined linear system Ax ≈ b find minimal corrections to the vector b and/or the matrix A such that the corrected system is consistent, such as the least squares (LS), the data least squares (DLS) and the total least squares (TLS). The scaled total least squares (STLS) method unifies the LS, DLS and TLS methods. The classical normwise condition numbers for the LS problem have been widely studied. However, there are no such similar results for the TLS and the STLS problems. In this paper, we first present a perturbation analysis of the STLS problem, which is a generalization of the TLS problem, and give a normwise condition number for the STLS problem. Different from normwise condition numbers, which measure the sizes of both input perturbations and output errors using some norms, componentwise condition numbers take into account the relation of each data component, and possible data sparsity. Then in this paper we give explicit expressions for the estimates of the mixed and componentwise condition numbers for the STLS problem. Since the TLS problem is a special case of the STLS problem, the condition numbers for the TLS problem follow immediately from our STLS results. All the discussions in this paper are under the Golub-Van Loan condition for the existence and uniqueness of the STLS solution. Yimin Wei is supported by the National Natural Science Foundation of China under grant 10871051, Shanghai Science & Technology Committee under grant 08DZ2271900 and Shanghai Education Committee under grant 08SG01. Sanzheng Qiao is partially supported by Shanghai Key Laboratory of Contemporary Applied Mathematics of Fudan University during his visiting.     

Structured condition numbers and statistical condition estimation for the LDU factorization

In this article, we consider the structured condition numbers for LDU, factorization by using the modified matrix-vector approach and the differential calculus, which can be represented by sets of parameters. By setting the specific norms and weight parameters, we present the expressions of the structured normwise, mixed, componentwise condition numbers and the corresponding results for unstructured ones. In addition, we investigate the statistical estimation of condition numbers of LDU factorization using the probabilistic spectral norm estimator and the small-sample statistical condition estimation method, and devise three algorithms. Finally, we compare the structured condition numbers with the corresponding unstructured ones in numerical experiments.     

Perturbation theory for the LDU factorization and accurate computations for diagonally dominant matrices

We present a structured perturbation theory for the LDU factorization of (row) diagonally dominant matrices and we use this theory to prove that a recent algorithm of Ye (Math Comp 77(264):2195–2230, 2008) computes the L, D and U factors of these matrices with relative errors less than 14n ³ u, where u is the unit roundoff and n × n is the size of the matrix. The relative errors for D are componentwise and for L and U are normwise with respect the “max norm” ||A||_M = max_ij |a_ij|{\|A\|_M = \max_{ij} |a_{ij}|}. These error bounds guarantee that for any diagonally dominant matrix A we can compute accurately its singular value decomposition and the solution of the linear system Ax = b for most vectors b, independently of the magnitude of the traditional condition number of A and in O(n ³) flops.     

Incremental Norm Estimation for Dense and Sparse Matrices

We present an incremental approach to 2-norm estimation for triangular matrices. Our investigation covers both dense and sparse matrices which can arise for example from a QR, a Cholesky or a LU factorization. If the explicit inverse of a triangular factor is available, as in the case of an implicit version of the LU factorization, we can relate our results to incremental condition estimation (ICE). Incremental norm estimation (INE) extends directly from the dense to the sparse case without needing the modifications that are necessary for the sparse version of ICE. INE can be applied to complement ICE, since the product of the two estimates gives an estimate for the matrix condition number. Furthermore, when applied to matrix inverses, INE can be used as the basis of a rank-revealing factorization.