Improving the stability and robustness of incomplete symmetric indefinite factorization preconditioners

Sparse symmetric indefinite linear systems of equations arise in numerous practical applications. In many situations, an iterative method is the method of choice but a preconditioner is normally required for it to be effective. In this paper, the focus is on a class of incomplete factorization algorithms that can be used to compute preconditioners for symmetric indefinite systems. A limited memory approach is employed that incorporates a number of new ideas with the goal of improving the stability, robustness, and efficiency of the preconditioner. These include the monitoring of stability as the factorization proceeds and the incorporation of pivot modifications when potential instability is observed. Numerical experiments involving test problems arising from a range of real‐world applications demonstrate the effectiveness of our approach.     

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.     

On the sensitivity of generators for the QR factorization of quasiseparable matrices with total nonpositivity

In this paper, we provide a relatively robust representation for the QR factorization of quasiseparable matrices with total nonpositivity. This representation allows us to develop a structure-preserving perturbation analysis. Consequently, stronger perturbation bounds are obtained to show that its generators determine the factors Q and R to high relative accuracy, independent of any conventional condition number. This means that it is possible to accurately compute the QR factorization by operating on these generators.     

Stability and Sensitivity of Tridiagonal LU Factorization without Pivoting

In this paper the accuracy of LU factorization of tridiagonal matrices without pivoting is considered. Two types of componentwise condition numbers for the L and U factors of tridiadonal matrices are presented and compared. One type is a condition number with respect to small relative perturbations of each entry of the matrix. The other type is a condition number with respect to small componentwise perturbations of the kind appearing in the backward error analysis of the usual algorithm for the LU factorization. We show that both condition numbers are of similar magnitude. This means that the algorithm is componentwise forward stable, i.e., the forward errors are of similar magnitude to those produced by a componentwise backward stable method. Moreover the presented condition numbers can be computed in O(n) flops, which allows to estimate with low cost the forward errors. AMS subject classification (2000) 65F35, 65F50, 15A12, 15A23, 65G50.Received October 2003. Accepted August 2004. Communicated by Per Christian Hansen.Froilán M. Dopico: This research has been partially supported by the Ministerio de Ciencia y Tecnología of Spain through grants BFM2003-06335-C03-02 (M. I. Bueno) and BFM2000-0008 (F. M. Dopico).     

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.     

Smoothed analysis of some condition numbers

In this note we do a smoothed analysis, in the sense of ( http://www‐math.mit.edu/～spielman/SmoothedAnalysis/ ), of the condition number for the Moore–Penrose inverse. Usual average analysis follows in a trivial manner as follow similar analyses for the condition number of the polar factorization. Copyright © 2005 John Wiley & Sons, Ltd.     

Using the Sherman-Morrison-Woodbury inversion formula for a fast solution of tridiagonal block Toeplitz systems

A fast numerical algorithm for solving systems of linear equations with tridiagonal block Toeplitz matrices is presented. The algorithm is based on a preliminary factorization of the generating quadratic matrix polynomial associated with the Toeplitz matrix, followed by the Sherman-Morrison-Woodbury inversion formula and solution of two bidiagonal and one diagonal block Toeplitz systems. Tight estimates of the condition numbers are provided for the matrix system and the main matrix systems generated during the preliminary factorization. The emphasis is put on rigorous stability analysis to rounding errors of the Sherman-Morrison-Woodbury inversion. Numerical experiments are provided to illustrate the theory.     

ON THE SENSITIVITY OF THE LDU FACTORIZATION

1　IntroductionG.W.Stewart,X.-W.Chang and A.Barralund etc.have done lot of perturbationanalyses on LU,QR and Cholesky factorizations( see[5] ,[6] ,[1 ] ,[2 ] ,[4 ] ,[3 ] ) .We givesensitivity analysisfor LDU factorization in this paper.The LDU factorization ( or LDMT) is an important method in numerical linear algebra( see [7] ) ,and can be viewed as the general form for LDLT factorization. The differencebetween LDU and LU factorizations in upper triangular matrix U,i.e. U is uni…     

The Numerical Factorization of Polynomials

Polynomial factorization in conventional sense is an ill-posed problem due to its discontinuity with respect to coefficient perturbations, making it a challenge for numerical computation using empirical data. As a regularization, this paper formulates the notion of numerical factorization based on the geometry of polynomial spaces and the stratification of factorization manifolds. Furthermore, this paper establishes the existence, uniqueness, Lipschitz continuity, condition number, and convergence of the numerical factorization to the underlying exact factorization, leading to a robust and efficient algorithm with a MATLAB implementation capable of accurate polynomial factorizations using floating point arithmetic even if the coefficients are perturbed.     

Fast accurate eigenvalue methods for graded positive definite matrices

Summary. Let where is a positive definite matrix and is diagonal and nonsingular. We show that if the condition number of is much less than that of then we can use algorithms based on the Cholesky factorization of to compute the eigenvalues of to high relative accuracy more efficiently than by Jacobi's method. The new methods are generally slower than tridiagonalization methods (which do not deliver the eigenvalues to maximal relative accuracy) but can be up to 4 times faster when the condition number of is very large. Received April 13, 1995     

Stability of Approximate Factorization with θ-Methods

Approximate factorization seems for certain problems a viable alternative to time splitting. Since a splitting error is avoided, accuracy will in general be favourable compared to time splitting methods. However, it is not clear to what extent stability is affected by factorization. Therefore we study here the effects of factorization on a simple, low order method, namely the -method. For this simple method it is possible to obtain rather precise results, showing limitations of the approximate factorization approach.     

The factorization method for cracks in inhomogeneous media

We consider the inverse scattering problem of determining the shape and location of a crack surrounded by a known inhomogeneous media. Both the Dirichlet boundary condition and a mixed type boundary conditions are considered. In order to avoid using the background Green function in the inversion process, a reciprocity relationship between the Green function and the solution of an auxiliary scattering problem is proved. Then we focus on extending the factorization method to our inverse shape reconstruction problems by using far field measurements at fixed wave number. We remark that this is done in a non intuitive space for the mixed type boundary condition as we indicate in the sequel.     

Wilkinson's inertia‐revealing factorization and its application to sparse matrices

We propose a new inertia‐revealing factorization for sparse symmetric matrices. The factorization scheme and the method for extracting the inertia from it were proposed in the 1960s for dense, banded, or tridiagonal matrices, but they have been abandoned in favor of faster methods. We show that this scheme can be applied to any sparse symmetric matrix and that the fill in the factorization is bounded by the fill in the sparse QR factorization of the same matrix (but is usually much smaller). We describe our serial proof‐of‐concept implementation and present experimental results, studying the method's numerical stability and performance.     

Factorization length distribution for affine semigroups I: Numerical semigroups with three generators

Most factorization invariants in the literature extract extremal factorization behavior, such as the maximum and minimum factorization lengths. Invariants of intermediate size, such as the mean, median, and mode factorization lengths are more subtle. We use techniques from analysis and probability to describe the asymptotic behavior of these invariants. Surprisingly, the asymptotic median factorization length is described by a number that is usually irrational.     

An incomplete factorization preconditioning method based on modification of element matrices

It is well known that standard incomplete factorization (IC) methods exist for M-matrices [15] and that modified incomplete factorization (MIC) methods exist for weakly diagonally dominant matrices [8]. The restriction to these classes of matrices excludes many realistic general applications to discretized partial differential equations. We present a technique to avoid this problem by making an initial modification already at the element level, followed by the standard IC or MIC factorization of the assembled matrix. This modification ensures weakly diagonally dominant M-matrices and is made in such a way that the condition number of the matrix is only increased by a constant factor independent of the mesh parameterh. Hence the fast convergence of the MICCG method, that is inO(h ^–1/2),h 0 iterations for second order elliptic problems, is preserved.     

Sweeping preconditioner for the Helmholtz equation: Hierarchical matrix representation

The paper introduces the sweeping preconditioner, which is highly efficient for iterative solutions of the variable‐coefficient Helmholtz equation including very‐high‐frequency problems. The first central idea of this novel approach is to construct an approximate factorization of the discretized Helmholtz equation by sweeping the domain layer by layer, starting from an absorbing layer or boundary condition. Given this specific order of factorization, the second central idea is to represent the intermediate matrices in the hierarchical matrix framework. In two dimensions, both the construction and the application of the preconditioners are of linear complexity. The generalized minimal residual method (GMRES) solver with the resulting preconditioner converges in an amazingly small number of iterations, which is essentially independent of the number of unknowns. This approach is also extended to the three‐dimensional case with some success. Numerical results are provided in both two and three dimensions to demonstrate the efficiency of this new approach. © 2011 Wiley Periodicals, Inc.     

Error bound of critical points and KL property of exponent 1/2 for squared F-norm regularized factorization

This paper is concerned with the squared F(robenius)-norm regularized factorization form for noisy low-rank matrix recovery problems. Under a suitable assumption on the restricted condition number of the Hessian matrix of the loss function, we establish an error bound to the true matrix for the non-strict critical points with rank not more than that of the true matrix. Then, for the squared F-norm regularized factorized least squares loss function, we establish its KL property of exponent 1/2 on the global optimal solution set under the noisy and full sample setting, and achieve this property at its certain class of critical points under the noisy and partial sample setting. These theoretical findings are also confirmed by solving the squared F-norm regularized factorization problem with an accelerated alternating minimization method.

     

连续代数扩域上多项式因式分解的Trager算法

多项式的因式分解是符号计算中最基本的算法,二十世纪六十年代开始出现的关于多项式因式分解的工作被认为是符号计算领域的起源．目前多项式的因式分解已经成熟,并已在Maple等符号计算软件中实现,但代数扩域上的因式分解算法还有待进一步改进．代数扩域上的基本算法是Trager算法．Weinberger等提出了基于Hensel提升的算法．这些算法是在单个扩域上做因式分解．而在吴零点分解定理中,多个代数扩域上的因式分解是非常基本的一步,主要用于不可约升列的计算．为了解决这一问题,吴文俊,胡森、王东明分别提出了基于方程求解的多个扩域上的因式分解算法．王东明、林东岱提出了另外一个算法Trager算法相似,将问题化为有理数域上的分解．他们应用了吴的三角化算法,因此算法的终止性依赖于吴方法的计算．支丽红则将提升技巧用于多个扩域上的因式分解算法．本文将Trager的算法直接推广为连续扩域上的因式分解,只涉及结式计算与有理数域上的因式分解,给出了多个代数扩域上的因式分解一个直接的算法．     

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.     

The Factorization Method for an Open Arc

We consider the inverse scattering problem of determining the shape of a thin dielectric infinite cylinder having an open arc as cross section. Assuming that the electric field is polarized in the TM mode, this leads to a mixed boundary value problem for the Helmholtz equation defined in the exterior of an open arc in $R^2$. We suppose that the arc has mixed Dirichlet-impedance boundary condition, and try to recover the shape of the arc through the far field pattern by using the factorization method. However, we are not able to apply the basic theorem introduced by Kirsch to treat the far field operator $F$, and some auxiliary operators have to be considered. The theoretical validation of the factorization method to our problem is given in this paper, and some numerical results are presented to show the viability of our method.