A preconditioning strategy for boundary element Galerkin methods

The Dirichlet and Neumann problems for the Laplacian are reformulated in the usual way as boundary integral equations of the first kind with symmetric kernels. These integral equations are solved using Galerkin's method with piecewise-constant and piecewise-linear boundary elements, respectively. In both cases, the stiffness matrix is symmetric and positive-definite, and has a condition number of order N, the number of degrees of freedom. By contrast, the condition number of the product of the two stiffness matrices is bounded independently of N. Hence, we can use the Neumann stiffness matrix to precondition the Dirichlet stiffness matrix, and vice versa. © 1997 John Wiley & Sons, Inc.     

非奇异阵特征极值和条件数的近似计算

本文从共轭梯度法的公式推导出对称正定阵A与三对角阵B的相似关系,B的元素由共轭梯度法的迭代参数确定.因此,对称正定阵的条件数计算可以化成三对角阵条件数的计算,并且可以在共轭梯度法的计算中顺带完成.它只需增加O(s)次的计算量,s为迭代次数.这与共轭梯度法的计算量相比是可以忽略的.当A为非对称正定阵时,只要A非奇异,即可用共轭梯度法计算ATA的特征极值和条件数,从而得出A的条件数.对不同算例的计算表明,这是一种快速有效的简便方法.     

Preconditioning techniques for an image deblurring problem

In this paper, we consider the solution of a large linear system of equations, which is obtained from discretizing the Euler–Lagrange equations associated with the image deblurring problem. The coefficient matrix of this system is of the generalized saddle point form with high condition number. One of the blocks of this matrix has the block Toeplitz with Toeplitz block structure. This system can be efficiently solved using the minimal residual iteration method with preconditioners based on the fast Fourier transform. Eigenvalue bounds for the preconditioner matrix are obtained. Numerical results are presented. Copyright © 2016 John Wiley & Sons, Ltd.     

边值问题离散系统数值稳定性的新度量

对于用有限元法或差分法求解微分方程边值问题,流行着这样的观点:当网格剖分出现小角度的三角形或窄长的矩形时,离散系统的数值稳定性就差.这种观点的根据是由于把系数矩阵条件数作为稳定性度量.     

On tridiagonal matrices unitarily equivalent to normal matrices

In this article the unitary equivalence transformation of normal matrices to tridiagonal form is studied.It is well-known that any matrix is unitarily equivalent to a tridiagonal matrix. In case of a normal matrix the resulting tridiagonal inherits a strong relation between its super- and subdiagonal elements. The corresponding elements of the super- and subdiagonal will have the same absolute value.In this article some basic facts about a unitary equivalence transformation of an arbitrary matrix to tridiagonal form are firstly studied. Both an iterative reduction based on Krylov sequences as a direct tridiagonalization procedure via Householder transformations are reconsidered. This equivalence transformation is then applied to the normal case and equality of the absolute value between the super- and subdiagonals is proved. Self-adjointness of the resulting tridiagonal matrix with regard to a specific scalar product is proved. Properties when applying the reduction on symmetric, skew-symmetric, Hermitian, skew-Hermitian and unitary matrices and their relations with, e.g., complex symmetric and pseudo-symmetric matrices are presented.It is shown that the reduction can then be used to compute the singular value decomposition of normal matrices making use of the Takagi factorization. Finally some extra properties of the reduction as well as an efficient method for computing a unitary complex symmetric decomposition of a normal matrix are given.     

Upper bounds for nearly optimal diagonal scaling of matrices

Optimal diagonal scaling of an n×n matrix A consists in finding a diagonal matrix D that minimizes a condition number of AD. Often a nearly optimal scaling of A is achieved by taking a diagonal matrix D₁ such that all diagonal elements of D₁A^TAD₁ are equal to one. It is shown in this paper that the condition number of AD₁ can be at least (n/2)^1/2 times the minimal one. Some questions for a further research are posed.     

A novel recursive subspace identification approach of closed-loop systems

In this paper, a subspace model identification method under closed-loop experimental condition is presented which can be implemented to recursively identify and update the system model. The projected matrices play an important role in this identification scheme which can be obtained by the projection of the input and output data onto the space of exogenous inputs and recursively updated through sliding window technique. The propagator type method in array signal processing is then applied to calculate the subspace spanned by the column vectors of the extended observability matrix without singular value decomposition. The speed of convergence of the proposed method is mainly dependent on the number of block Hankel matrix rows and the initialization accuracy of the projected data matrices. The proposed method is feasible for the closed-loop system contaminated with coloured noises. Two numerical examples show the effectiveness of the proposed algorithm.     

预条件同时置换(PSD)迭代法的收敛性分析

1引言求解线性方程组Ax=6,(1.1)其中A∈R~(n×n)非奇异阵且对角元非零,x,b∈R~n,x未知,b已知.不失一般性,我们假设A=I-L-U,(1.2)其中L,U分别为A的严格下和上三角矩阵,相应的Jacobi迭代矩阵为B=L U.(1.3)若Q是非奇异阵且Q~(-1)易计算,于是(1.1)可以变成     

A non-conforming domain decomposition for Raviart-Thomas vector fields in three dimensions

In this paper we are concerned with a domain decomposition method with nonmatching grids for Raviart-Thomas finite elements. In this method, the normal complement of the resulting approximation is not continuous across the interface. To handle such non-conformity, a new matching condition will be introduced. Such matching condition still     

COMBINATIVE PRECONDITIONERS OF MODIFIED INCOMPLETE CHOLESKY FACTORIZATION AND SHERMAN-MORRISON-WOODBURY UPDATE FOR SELF-ADJOINT ELLIPTIC DIRICHLET-PERIODIC BOUNDARY VALUE PROBLEMS

For the system of linear equations arising from discretization of the second-order self-adjoint elliptic Dirichlet-periodic boundary value problems,by making use of the specialstructure of the coefficient matrix we present a class of combinative preconditioners whichare technical combinations of modified incomplete Cholesky factorizations and Sherman-Morrison-Woodbury update.Theoretical analyses show that the condition numbers of thepreconditioned matrices can be reduced to(?)(h~(-1)),one order smaller than the conditionnumber(?)(h~(-2))of the original matrix.Numerical implementations show that the resultingpreconditioned conjugate gradient methods are feasible,robust and efficient for solving thisclass of linear systems.     

A non-conforming domain decomposition for Raviart-Thomas vector fields in three dimensions

In this paper we are concerned with a domain decomposition method with non-matching grids for Raviart-Thomas finite elements. In this method, the normal complement of the resulting approximation is not continuous across the interface. To handle such non-conformity, a new matching condition will be introduced. Such matching condition still results in a symmetric and positive definite stiffness matrix. It will be shown that the approximate solution generated by the domain decomposition possesses the optimal energy error estimate.     

Convergence of algebraic multigrid based on smoothed aggregation

Summary. We prove an abstract convergence estimate for the Algebraic Multigrid Method with prolongator defined by a disaggregation followed by a smoothing. The method input is the problem matrix and a matrix of the zero energy modes of the same problem but with natural boundary conditions. The construction is described in the case of a general elliptic system. The condition number bound increases only as a polynomial of the number of levels, and requires only a uniform weak approximation property for the aggregation operators. This property can be a-priori verified computationally once the aggregates are known. For illustration, it is also verified here for a uniformly elliptic diffusion equations discretized by linear conforming quasiuniform finite elements. Only very weak and natural assumptions on the hierarchy of aggregates are needed. Received March 1, 1998 / Revised version received January 28, 2000 / Published online: December 19, 2000     

The interpolation problem for ridge functions

It is shown that the interpolation problem for ridge functions can be solved if and only if the rank of a certain matrix A equals the number of interpolation points. The elements of the matrix A are either 0 or 1 and can be easilyfound from the arguments of the unknown functions. It is shown that Sun's Characteristic, or incidence matrix C is given by C = AA ^T . From this it follows that the rank condition is equivalent to Sun's positive definite C condition.     

Tridiagonal preconditioning for Poisson-like difference equations with flat grids: Application to incompressible atmospheric flow

The convergence of many iterative procedures, in particular that of the conjugate gradient method, strongly depends on the condition number of the linear system to be solved. In cases with a large condition number, therefore, preconditioning is often used to transform the system into an equivalent one, with a smaller condition number and therefore faster convergence. For Poisson-like difference equations with flat grids, the vertical part of the difference operator is dominant and tridiagonal and can be used for preconditioning. Such a procedure has been applied to incompressible atmospheric flows to preserve incompressibility, where a system of Poisson-like difference equations is to be solved for the dynamic pressure part. In the mesoscale atmospheric model KAMM, convergence has been speeded up considerably by tridiagonal preconditioning, even though the system matrix is not symmetric and, hence, the biconjugate gradient method must be used.     

Tridiagonal preconditioning for Poisson-like difference equations with flat grids: Application to incompressible atmospheric flow

The convergence of many iterative procedures, in particular that of the conjugate gradient method, strongly depends on the condition number of the linear system to be solved. In cases with a large condition number, therefore, preconditioning is often used to transform the system into an equivalent one, with a smaller condition number and therefore faster convergence. For Poisson-like difference equations with flat grids, the vertical part of the difference operator is dominant and tridiagonal and can be used for preconditioning. Such a procedure has been applied to incompressible atmospheric flows to preserve incompressibility, where a system of Poisson-like difference equations is to be solved for the dynamic pressure part. In the mesoscale atmospheric model KAMM, convergence has been speeded up considerably by tridiagonal preconditioning, even though the system matrix is not symmetric and, hence, the biconjugate gradient method must be used.     

Exact bounds for the sensitivity analysis of structures with uncertain-but-bounded parameters

Based on interval mathematical theory, the interval analysis method for the sensitivity analysis of the structure is advanced in this paper. The interval analysis method deals with the upper and lower bounds on eigenvalues of structures with uncertain-but-bounded (or interval) parameters. The stiffness matrix and the mass matrix of the structure, whose elements have the initial errors, are unknown except for the fact that they belong to given bounded matrix sets. The set of possible matrices can be described by the interval matrix. In terms of structural parameters, the stiffness matrix and the mass matrix take the non-negative decomposition. By means of interval extension, the generalized interval eigenvalue problem of structures with uncertain-but-bounded parameters can be divided into two generalized eigenvalue problems of a pair of real symmetric matrix pair by the real analysis method. Unlike normal sensitivity analysis method, the interval analysis method obtains informations on the response of structures with structural parameters (or design variables) changing and without any partial differential operation. Low computational effort and wide application rang are the characteristic of the proposed method. Two illustrative numerical examples illustrate the efficiency of the interval analysis.     

On the distance to uncontrollability and the distance to instability and their relation to some condition numbers in control

Summary. According to the methodology of [6], many measures of distance arising in problems in numerical linear algebra and control can be bounded by a factor times the reciprocal of an appropriate condition number, where the distance is thought of as the distance between a given problem to the nearest ill-posed problem. In this paper, four major problems in numerical linear algebra and control are further considered: the computation of system Hessenberg form, the solution of the algebraic Riccati equation, the pole assignment problem and the matrix exponential. The distances considered here are the distance to uncontrollability and the distance to instability. Received November 4, 1995 / Revised version received March 4, 1996     

A comparison of abstract versions of deflation,balancing and additive coarse grid correction preconditioners

In this paper we consider various preconditioners for the conjugate gradient (CG) method to solve large linear systems of equations with symmetric positive definite system matrix. We continue the comparison between abstract versions of the deflation, balancing and additive coarse grid correction preconditioning techniques started in (SIAM J. Numer. Anal. 2004; 42 :1631–1647; SIAM J. Sci. Comput. 2006; 27 :1742–1759). There the deflation method is compared with the abstract additive coarse grid correction preconditioner and the abstract balancing preconditioner. Here, we close the triangle between these three methods. First of all, we show that a theoretical comparison of the condition numbers of the abstract additive coarse grid correction and the condition number of the system preconditioned by the abstract balancing preconditioner is not possible. We present a counter example, for which the condition number of the abstract additive coarse grid correction preconditioned system is below the condition number of the system preconditioned with the abstract balancing preconditioner. However, if the CG method is preconditioned by the abstract balancing preconditioner and is started with a special starting vector, the asymptotic convergence behavior of the CG method can be described by the so‐called effective condition number with respect to the starting vector. We prove that this effective condition number of the system preconditioned by the abstract balancing preconditioner is less than or equal to the condition number of the system preconditioned by the abstract additive coarse grid correction method. We also provide a short proof of the relationship between the effective condition number and the convergence of CG. Moreover, we compare the A‐norm of the errors of the iterates given by the different preconditioners and establish the orthogonal invariants of all three types of preconditioners. Copyright © 2008 John Wiley & Sons, Ltd.     

On a Sparse Representation of an n-Dimensional Laplacian in Wavelet Coordinates

Important parts of adaptive wavelet methods are well-conditioned wavelet stiffness matrices and an efficient approximate multiplication of quasi-sparse stiffness matrices with vectors in wavelet coordinates. Therefore it is useful to develop a well-conditioned wavelet basis with respect to which both the mass and stiffness matrices are sparse in the sense that the number of nonzero elements in each column is bounded by a constant. Consequently, the stiffness matrix corresponding to the n-dimensional Laplacian in the tensor product wavelet basis is also sparse. Then a matrix–vector multiplication can be performed exactly with linear complexity. In this paper, we construct a wavelet basis based on Hermite cubic splines with respect to which both the mass matrix and the stiffness matrix corresponding to a one-dimensional Poisson equation are sparse. Moreover, a proposed basis is well-conditioned on low decomposition levels. Small condition numbers for low decomposition levels and a sparse structure of stiffness matrices are kept for any well-conditioned second order partial differential equations with constant coefficients; furthermore, they are independent of the space dimension.     

Mixed,componentwise condition numbers and small sample statistical condition estimation of Sylvester equations

We present a componentwise perturbation analysis for the continuous‐time Sylvester equations. Componentwise, mixed condition numbers and new perturbation bounds are derived for the matrix equations. The small sample statistical method can also be applied for the condition estimation. These condition numbers and perturbation bounds are tested on numerical examples and compared with the normwise condition number. The numerical examples illustrate that the mixed condition number gives sharper bounds than the normwise one. Copyright © 2011 John Wiley & Sons, Ltd.