广义Cholesky分解乘法扰动分析

0引言关于实对称矩阵的广义Cholesky分解和扰动问题是矩阵计算的重要问题,可参考文献[1-2].本文首先介绍已有的采用加法扰动的角度得到的广义Cholesky分解的一阶相对     

The Equality Constrained Indefinite Least Squares Problem: Theory and Algorithms

We present theory and algorithms for the equality constrained indefinite least squares problem, which requires minimization of an indefinite quadratic form subject to a linear equality constraint. A generalized hyperbolic QR factorization is introduced and used in the derivation of perturbation bounds and to construct a numerical method. An alternative method is obtained by employing a generalized QR factorization in combination with a Cholesky factorization. Rounding error analysis is given to show that both methods have satisfactory numerical stability properties and numerical experiments are given for illustration. This work builds on recent work on the unconstrained indefinite least squares problem by Chandrasekaran, Gu, and Sayed and by the present authors.     

对称不定矩阵的广义Cholesky分解法

对称不定矩阵的广义Ｃｈｏｌｅｓｋｙ分解法赵金熙（南京大学）ＴＨＥＧＥＮＥＲＡＬＩＺＥＤＣＨＯＬＳＫＹＦＡＣＴＯＲＩＺＡＴＩＯＮＭＥＴＨＯＤＦＯＲＳＯＬＶＩＮＧＳＹＭＭＥＴＲＩＣＩＮＤＥＦＩＮＩＴＥＬＩＮＥＡＲＳＹＳＴＥＭＳ￥ＺｈａｏＪｉｎ－ｘｉ（Ｎａ...     

Sylvester方程在矩阵扰动分析中的应用

§1.引言 矩阵扰动分析的研究对于矩阵论的发展及数值分析问题计算结果的分析和处理都有重要意义.有关特征值、广义特征值及最小二乘问题的主要研究结果均含于[1]中,[5]运用二次方程根的判别法通过对代数Ricatti方程的解的估计给出了QR分解因子及Cholesky因子的扰动分析,但论证方法及所得结果都比较复杂且所求条件很强.[3]和     

A multilevel block incomplete cholesky preconditioner for solving normal equations in linear least squares problems

An incomplete factorization method for preconditioning symmetric positive definite matrices is introduced to solve normal equations. The normal equations are form to solve linear least squares problems. The procedure is based on a block incomplete Cholesky factorization and a multilevel recursive strategy with an approximate Schur complement matrix formed implicitly. A diagonal perturbation strategy is implemented to enhance factorization robustness. The factors obtained are used as a preconditioner for the conjugate gradient method. Numerical experiments are used to show the robustness and efficiency of this preconditioning technique, and to compare it with two other preconditioners.     

大型对称不定箭形线性方程组的分解方法

1 引言 首先考虑2×2矩阵 显然当k>1/2时,矩阵K是对称正定的,且K可以分解成Cholesky因子:当k=1/2时,K为奇异矩阵;而当k<1/2时,K为对称不定矩阵,这时K有广义Cholesky分解式:并且这种分解是稳定的,一般地我们给出定义 定义1.1 设有矩阵K∈R~((m+n)×(m+n)),若总存在排列矩阵P∈R~((m+n)×(m+n))和对称正定矩阵H∈R~(m×n)、G∈R(m×m)使得则称矩阵K为对称拟定(Symmetric quasidefinite)矩阵。     

On the Solution of a Class of Toeplitz Systems

The solution of certain Toeplitz linear systems is considered in this paper. This kind of systems are encountered when we solve certain partial differential equations by finite difference techniques and approximate functions using higher order splines. The methods presented here are more efficient than the Cholesky decomposition method and are based on the circulant factorization of the symmetric "banded circulant" matrix, the Woodbury formula and the algebraic perturbation method.     

A note on factoring 0-1 matrices

Nonnegative definite 0-1 matrices are shown to have a Cholesky factorization with the factors being 0-1 matrices. Conditions are derived for the existence of a "Cholesky" factorization of symmetric Boolean matrices. This condition is related to the structure of the graph associated with the matrix.     

A product-form Cholesky factorization method for handling dense columns in interior point methods for linear programming

Cholesky factorization has become the method of choice for solving the symmetric system of linear equations arising in interior point methods (IPMs) for linear programming (LP), its main advantages being numerical stability and efficiency for sparse systems. However in the presence of dense columns there is dramatic loss of efficiency. A typical approach to remedy this problem is to apply the Sherman-Morrison-Woodbury (SMW) update formula to the dense part. This approach while being very efficient, is not numerically stable. Here we propose using product-form Cholesky factorization to handle dense columns. The proposed approach is essentially as stable as the original Cholesky factorization and nearly as efficient as the SMW approach. We demonstrate these properties both theoretically and computationally. A key part of our theoretical analysis is the proof that the elements of the Cholesky factors of the matrices that arise in IPMs for LP are uniformly bounded as the duality gap converges to zero.The doctoral research of this author was supported in part by an IBM Cooperative FellowshipResearch supported in part by NSF Grants DMS 91-06195, DMS 94-14438, DMS 95-27124, DMS 01-04282 and CDA 97-26385 and DOE Grant DE-FG02-92ER25126     

Generalized matrix inversion is not harder than matrix multiplication

Starting from the Strassen method for rapid matrix multiplication and inversion as well as from the recursive Cholesky factorization algorithm, we introduced a completely block recursive algorithm for generalized Cholesky factorization of a given symmetric, positive semi-definite matrix A∈R^n×n$A\in {\mathbb{R}}^{n\times n}$. We used the Strassen method for matrix inversion together with the recursive generalized Cholesky factorization method, and established an algorithm for computing generalized {2,3}$\{2,3\}$ and {2,4}$\{2,4\}$ inverses. Introduced algorithms are not harder than the matrix–matrix multiplication.     

Modified Gram-Schmidt-based methods for block downdating the Cholesky factorization

The hyperbolic modified Gram-Schmidt (HMGS) method is proposed for block downdating the Cholesky factorization. The method might be unsatisfactory due to rounding errors. A modified version based on the MGS process is presented and is shown to be mixed stable. Numerical tests show that the new method has the same numerical properties as the generalized LINPACK-type algorithm, and can work better than the Householder-based algorithm given by Bojanczyk and Steinhardt (1991) [9].     

Accuracy and Stability of the Null Space Method for Solving the Equality Constrained Least Squares Problem

The null space method is a standard method for solving the linear least squares problem subject to equality constraints (the LSE problem). We show that three variants of the method, including one used in LAPACK that is based on the generalized QR factorization, are numerically stable. We derive two perturbation bounds for the LSE problem: one of standard form that is not attainable, and a bound that yields the condition number of the LSE problem to within a small constant factor. By combining the backward error analysis and perturbation bounds we derive an approximate forward error bound suitable for practical computation. Numerical experiments are given to illustrate the sharpness of this bound.     

On the Cholesky factorization of the Gram matrix of locally supported functions

Cholesky factorization of bi-infinite and semi-infinite matrices is studied and in particular the following is proved. If a bi-infinite matrixA has a Cholesky factorization whose lower triangular factorL and its lower triangular inverse decay exponentially away from the diagonal, then the semi-infinite truncation ofA has a lower triangular Cholesky factor whose elements approach those ofL exponentially. This result is then applied to studying the asymptotic behavior of splines obtained by orthogonalizing a large finite set of B-splines, in particular identifying the limiting profile when the knots are equally spaced.The first and second authors were partially supported by Nato Grant #920209, the second author also by the Alexander von Humboldt Foundation, and the last two authors by the Italian Ministry of University and Scientific and Technological Research.     

Perturbation analysis for block downdating of a Cholesky decomposition

Summary. Let the Cholesky decomposition of be , where is upper triangular. The Cholesky block downdating problem is to determine such that , where is a block of rows from the data matrix . We analyze the sensitivity of this block downdating problem of the Cholesky factorization. A measure of conditioning for the Cholesky block downdating is presented and compared to the single row downdating case. Received September 15, 1993     

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.     

A fast algorithm for subspace state-space system identification via exploitation of the displacement structure

Two recent approaches (Van Overschee, De Moor, N4SID, Automatica 30 (1) (1994) 75; Verhaegen, Int. J. Control 58(3) (1993) 555) in subspace identification problems require the computation of the R factor of the QR factorization of a block-Hankel matrix H, which, in general has a huge number of rows. Since the data are perturbed by noise, the involved matrix H is, in general, full rank. It is well known that, from a theoretical point of view, the R factor of the QR factorization of H is equivalent to the Cholesky factor of the correlation matrix H^TH, apart from a multiplication by a sign matrix. In Sima (Proceedings Second NICONET Workshop, Paris-Versailles, December 3, 1999, p. 75), a fast Cholesky factorization of the correlation matrix, exploiting the block-Hankel structure of H, is described. In this paper we consider a fast algorithm to compute the R factor based on the generalized Schur algorithm. The proposed algorithm allows to handle the rank–deficient case.     

Flexible incomplete Cholesky factorization with multi‐parameters to control the number of nonzero elements in preconditioners

An incomplete Cholesky (IC) factorization with multi‐parameters is presented. The marked virtue of the proposed IC factorization algorithm is to dynamically control the number of nonzero elements in each column of the IC factorization preconditioner L with the help of these involved parameters. Parameter setting strategies are also given. Numerical results show that the total computing time for both computation of the preconditioner L and iterative solution is evidently reduced for almost all test matrices. In general, these parameters can obviously enhance the effectiveness and performance of the IC factorization. Copyright © 2011 John Wiley & Sons, Ltd.     

Perturbation analysis for the symplectic QR factorization

In this paper, the perturbation analysis for the symplectic QR factorization is considered. Some first-order and rigorous normwise perturbation bounds with normwise or componentwise perturbations in the given matrix are presented.     

On the stability of the incomplete Cholesky decomposition for a singular perturbed problem,where the coefficient matrix is not an M-matrix

The incomplete Cholesky decomposition is known as an excellent smoother in a multigrid iteration and as a preconditioner for the conjugate gradient method. However, the existence of the decomposition is only ensured if the system matrix is an M-matrix. It is well-known that finite element methods usually do not lead to M-matrices. In contrast to this restricting fact, numerical experiments show that, even in cases where the system matrix is not an M-matrix the behaviour of the incomplete Cholesky decomposition apparently does not depend on the structure of the grid. In this paper the behaviour of the method is investigated theoretically for a model problem, where the M-matrix condition is violated systematically by a suitable perturbation. It is shown that in this example the stability of the incomplete Cholesky decomposition is independent of the perturbation and that the analysis of the smoothing property can be carried through. This can be considered as a generalization of the results for the so called square-grid triangulation, as has been established by Wittum in [12] and [11].     

Using a hybrid preconditioner for solving large-scale linear systems arising from interior point methods

We devise a hybrid approach for solving linear systems arising from interior point methods applied to linear programming problems. These systems are solved by preconditioned conjugate gradient method that works in two phases. During phase I it uses a kind of incomplete Cholesky preconditioner such that fill-in can be controlled in terms of available memory. As the optimal solution of the problem is approached, the linear systems becomes highly ill-conditioned and the method changes to phase II. In this phase a preconditioner based on the LU factorization is found to work better near a solution of the LP problem. The numerical experiments reveal that the iterative hybrid approach works better than Cholesky factorization on some classes of large-scale problems.