Convergence of Rump’s method for computing the Moore-Penrose inverse

We extend Rump’s verified method (S.Oishi, K.Tanabe, T.Ogita, S.M.Rump (2007)) for computing the inverse of extremely ill-conditioned square matrices to computing the Moore-Penrose inverse of extremely ill-conditioned rectangular matrices with full column (row) rank. We establish the convergence of our numerical verified method for computing the Moore-Penrose inverse. We also discuss the rank-deficient case and test some ill-conditioned examples. We provide our Matlab codes for computing the Moore-Penrose inverse.     

Ill-Conditionedness Need not be Componentwise Near to Ill-Posedness for Least Squares Problems

The condition number of a problem measures the sensitivity of the answer to small changes in the input, where small refers to some distance measure. A problem is called ill-conditioned if the condition number is large, and it is called ill-posed if the condition number is infinity. It is known that for many problems the (normwise) distance to the nearest ill-posed problem is proportional to the reciprocal of the condition number. Recently it has been shown that for linear systems and matrix inversion this is also true for componentwise distances. In this note we show that this is no longer true for least squares problems and other problems involving rectangular matrices. Problems are identified which are arbitrarily ill-conditioned (in a componentwise sense) whereas any componentwise relative perturbation less than 1 cannot produce an ill-posed problem. Bounds are given using additional information on the matrix.     

Generalization of a Parametric Fixed‐Point Iteration

Based on new sufficient regularity conditions, Rump's method for solving parametric interval linear systems is generalized which expands its scope of applicability over a class of co‐called column‐dependent parametric matrices. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Optimally scaled and optimally conditioned Vandermonde and Vandermonde-like matrices

Vandermonde matrices with real nodes are known to be severely ill-conditioned. We investigate numerically the extent to which the condition number of such matrices can be reduced, either by row-scaling or by optimal configurations of nodes. In the latter case we find empirically the condition of the optimally conditioned n×n Vandermonde matrix to grow exponentially at a rate slightly less than \((1+\sqrt{2})^{n}\). Much slower growth—essentially linear—is observed for optimally conditioned Vandermonde-Jacobi matrices. We also comment on the computational challenges involved in determining condition numbers of highly ill-conditioned matrices.     

Convergence of the Multigrid Method of Ill-conditioned Block Toeplitz Systems

We study the solutions of block Toeplitz systems A _mn u = b by the multigrid method (MGM). Here the block Toeplitz matrices A _mn are generated by a nonnegative function f (x,y) with zeros. Since the matrices A _mn are ill-conditioned, the convergence factor of classical iterative methods will approach 1 as the size of the matrices becomes large. These classical methods, therefore, are not applicable for solving ill-conditioned systems. The MGM is then proposed in this paper. For a class of block Toeplitz matrices, we show that the convergence factor of the two-grid method (TGM) is uniformly bounded below 1 independent of mn and the full MGM has convergence factor depending only on the number of levels. The cost per iteration for the MGM is of O(mn log mn) operations. Numerical results are given to explain the convergence rate.     

Analysis of the GCR method with mixed precision arithmetic using QuPAT

To verify computation results of double precision arithmetic, a high precision arithmetic environment is needed. However, it is difficult to use high precision arithmetic in ordinary computing environments without any special hardware or libraries. Hence, we designed the quadruple precision arithmetic environment QuPAT on Scilab to satisfy the following requirements: (i) to enable programs to be written simply using quadruple precision arithmetic; (ii) to enable the use of both double and quadruple precision arithmetic at the same time; (iii) to be independent of any hardware and operating systems.To confirm the effectiveness of QuPAT, we applied the GCR method for ill-conditioned matrices and focused on the scalar parameters α and β in GCR, partially using DD arithmetic. We found that the use of DD arithmetic only for β leads to almost the same results as when DD arithmetic is used for all computations. We conclude that QuPAT is an excellent interactive tool for using double precision and DD arithmetic at the same time.     

Convergence of a large time step generalization of Godunov's method for conservation laws

A natural generalization of Godunov's method for Courant numbers larger than 1 is obtained by handling interactions between neighboring Riemann problems linearly, i.e., by allowing waves to pass through one another with no change in strength or speed. This method is well defined for arbitrarily large Courant numbers and can be written in conservation form. It follows that if a sequence of approximations converges to a limit u(x,t) as the mesh is refined, then u is a weak solution to the system of conservation laws. For scalar problems the method is total variation diminishing and every sequence contains a convergent subsequence. It is conjectured that in fact every sequence converges to the (unique) entropy solution provided the correct entropy solution is used for each Riemann problem. If the true Riemann solutions are replaced by approximate Riemann solutions which are consistent with the conservation law, then the above convergence results for general systems continue to hold.     

Reducing the ill conditioning in the method of fundamental solutions

The method of fundamental solutions (MFS) is a meshless method for solving boundary value problems with some partial differential equations. It allows to obtain highly accurate approximations for the solutions assuming that they are smooth enough, even with small matrices. As a counterpart, the (dense) matrices involved are often ill-conditioned which is related to the well known uncertainty principle stating that it is impossible to have high accuracy and good conditioning at the same time. In this work, we propose a technique to reduce the ill conditioning in the MFS, assuming that the source points are placed on a circumference of radius R. The idea is to apply a suitable change of basis that provides new basis functions that span the same space as the MFS’s, but are much better conditioned. In the particular case of circular domains, the algorithm allows to obtain errors close to machine precision, with condition numbers of order O(1), independently of the number of points sources and R.     

A numerical algorithm to reduce ill-conditioning in meshless methods for the Helmholtz equation

Some meshless methods have been applied to the numerical solution of boundary value problems involving the Helmholtz equation. In this work, we focus on the method of fundamental solutions and the plane waves method. It is well known that these methods can be highly accurate assuming smoothness of the domains and the boundary data. However, the matrices involved are often ill-conditioned and the effect of this ill-conditioning may drastically reduce the accuracy. In this work, we propose a numerical algorithm to reduce the ill-conditioning in both methods. The idea is to perform a suitable change of basis. This allows to obtain new basis functions that span exactly the same space as the original meshless method, but are much better conditioned. In the case of circular domains, this technique allows to obtain errors close to machine precision, with condition numbers of order O(1), independently of the number of basis functions in the expansion.     

On convergent numerical algorithms for unsymmetric collocation

In this paper, we are interested in some convergent formulations for the unsymmetric collocation method or the so-called Kansa’s method. We review some newly developed theories on solvability and convergence. The rates of convergence of these variations of Kansa’s method are examined and verified in arbitrary–precision computations. Numerical examples confirm with the theories that the modified Kansa’s method converges faster than the interpolant to the solution; that is, exponential convergence for the multiquadric and Gaussian radial basis functions (RBFs). Some numerical algorithms are proposed for efficiency and accuracy in practical applications of Kansa’s method. In double–precision, even for very large RBF shape parameters, we show that the modified Kansa’s method, through a subspace selection using a greedy algorithm, can produce acceptable approximate solutions. A benchmark algorithm is used to verify the optimality of the selection process.     

Using Local Spectral Information in Domain Decomposition Methods – A Brief Overview in a Nutshell

For second-order elliptic partial differential equations large discontinuities in the coefficients yield ill-conditioned stiffness matrices. The convergence of domain decomposition methods (DDM) can be improved by incorporating (numerically computed) local eigenvectors into the coarse space. Different adaptive coarse spaces for DDM have been constructed and used successfully. For two-level Schwarz, FETI-1 and BDD methods, adaptive coarse spaces with a rigorous theoretical basis are known for 2D and 3D. Although successfully in use for almost a decade, a theory for adaptive coarse spaces for FETI-DP and BDDC was lacking. While the problem was recently settled for 2D, the estimate for the 3D adaptive algorithm required improved coarse spaces. We give an brief overview of the literature, i. e., the different known approaches, and show numerical results for a specific adaptive FETI-DP method in 3D, where the condition number bound could only recently be proven. (© 2016 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

影响阻尼牛顿法收敛性的两个重要参数

对阻尼牛顿算法作了适当的改进,证明了新算法的收敛性.基于新算法,运用计算机代数系统Matlab,研究了迭代次数k,参数对(μ,λ)与初值x0三者间的依赖关系,研究了病态问题在新算法下趋于稳定的渐变(瞬变)过程.数值结果表明:(1)阻尼牛顿迭代中,参数对(μ,λ)与迭代次数k间存在特有的非线性关系;(2)适当的参数对(μ,λ)与阻尼因子α的共同作用能够在迭代中大幅度地降低病态问题的Jacobi阵的条件数,使病态问题逐渐趋于稳定,从而改变原问题的收敛性与收敛速度.     

The convergence of Jacobi–Davidson iterations for Hermitian eigenproblems

Rayleigh quotient iteration is an iterative method with some attractive convergence properties for finding (interior) eigenvalues of large sparse Hermitian matrices. However, the method requires the accurate (and, hence, often expensive) solution of a linear system in every iteration step. Unfortunately, replacing the exact solution with a cheaper approximation may destroy the convergence. The (Jacobi‐) Davidson correction equation can be seen as a solution for this problem. In this paper we deduce quantitative results to support this viewpoint and we relate it to other methods. This should make some of the experimental observations in practice more quantitative in the Hermitian case. Asymptotic convergence bounds are given for fixed preconditioners and for the special case if the correction equation is solved with some fixed relative residual precision. A dynamic tolerance is proposed and some numerical illustration is presented. Copyright © 2002 John Wiley & Sons, Ltd.     

On condition numbers of a nondefective multiple eigenvalue

Summary This paper concerns with measures of the sensitivity of a nondefective multiple eigenvalue of a matrix. Different condition numbers are introduced starting from directional derivatives of the multiple eigenvalue. Properties of the condition numbers defined by Stewart and Zhang [4] are studied; especially, the Wilkinson's theorem on matrices with a very ill-conditioned eigenproblem is extended.This research was supported by the Institute for Advanced Computer Studies of the University of Maryland and the Swedish Natural Science Research Council     

A regularized limited memory BFGS method for nonconvex unconstrained minimization

The limited memory BFGS method (L-BFGS) is an adaptation of the BFGS method for large-scale unconstrained optimization. However, The L-BFGS method need not converge for nonconvex objective functions and it is inefficient on highly ill-conditioned problems. In this paper, we proposed a regularization strategy on the L-BFGS method, where the used regularization parameter may play a compensation role in some sense when the condition number of Hessian approximation tends to become ill-conditioned. Then we proposed a regularized L-BFGS method and established its global convergence even when the objective function is nonconvex. Numerical results show that the proposed method is efficient.     

Error-free transformations of matrix multiplication by using fast routines of matrix multiplication and its applications

This paper is concerned with accurate matrix multiplication in floating-point arithmetic. Recently, an accurate summation algorithm was developed by Rump et al. (SIAM J Sci Comput 31(1):189–224, 2008). The key technique of their method is a fast error-free splitting of floating-point numbers. Using this technique, we first develop an error-free transformation of a product of two floating-point matrices into a sum of floating-point matrices. Next, we partially apply this error-free transformation and develop an algorithm which aims to output an accurate approximation of the matrix product. In addition, an a priori error estimate is given. It is a characteristic of the proposed method that in terms of computation as well as in terms of memory consumption, the dominant part of our algorithm is constituted by ordinary floating-point matrix multiplications. The routine for matrix multiplication is highly optimized using BLAS, so that our algorithms show a good computational performance. Although our algorithms require a significant amount of working memory, they are significantly faster than ‘gemmx’ in XBLAS when all sizes of matrices are large enough to realize nearly peak performance of ‘gemm’. Numerical examples illustrate the efficiency of the proposed method.     

Solution to the Neumann problem exterior to a prolate spheroid by radial basis functions

We consider the exterior Neumann problem of the Laplacian with boundary condition on a prolate spheroid. We propose to use spherical radial basis functions in the solution of the boundary integral equation arising from the Dirichlet–to–Neumann map. Our approach is particularly suitable for handling of scattered data, e.g. satellite data. We also propose a preconditioning technique based on domain decomposition method to deal with ill-conditioned matrices arising from the approximation problem.     

ℋ︁‐matrices for the convection‐diffusion equation

Hierarchical matrices (ℋ︁‐matrices) provide a technique for the sparse approximation of large, fully populated matrices. This technique has been shown to be applicable to stiffness matrices arising in boundary element method applications where the kernel function displays certain smoothness properties. The error estimates for an approximation of the kernel function by a separable function can be carried over directly to error estimates for an approximation of the stiffness matrix by an ℋ︁‐matrix, using a certain standard partitioning and admissibility condition for matrix blocks. Similarly, ℋ︁‐matrix techniques can be applied in the finite element context where it is the inverse of the stiffness matrix that is fully populated. Here one needs a separable approximation of Green's function of the underlying boundary value problem in order to prove approximability by matrix blocks of low rank. Unfortunately, Green's function for the convection‐diffusion equation does not satisfy the required smoothness properties, hence prohibiting a straightforward generalization of the separable approximation through Taylor polynomials. We will use Green's function to motivate a modification in the (hierarchical) partitioning of the index set and as a consequence the resulting hierarchy of block partitionings as well as the admissibility condition. We will illustrate the effect of the proposed modifications by numerical results.     

二、三阶可逆矩阵可以相似对角化的几何条件

从几何的角度给出了特征值不含1的二、三阶可逆矩阵可以相似对角化的一个充分条件和二、三阶可逆矩阵可以相似对角化的一个充分必要条件.     

Preconditioned iterative methods for a class of nonlinear eigenvalue problems

This paper proposes new iterative methods for the efficient computation of the smallest eigenvalue of symmetric nonlinear matrix eigenvalue problems of large order with a monotone dependence on the spectral parameter. Monotone nonlinear eigenvalue problems for differential equations have important applications in mechanics and physics. The discretization of these eigenvalue problems leads to nonlinear eigenvalue problems with very large sparse ill-conditioned matrices monotonically depending on the spectral parameter. To compute the smallest eigenvalue of large-scale matrix nonlinear eigenvalue problems, we suggest preconditioned iterative methods: preconditioned simple iteration method, preconditioned steepest descent method, and preconditioned conjugate gradient method. These methods use only matrix-vector multiplications, preconditioner-vector multiplications, linear operations with vectors, and inner products of vectors. We investigate the convergence and derive grid-independent error estimates for these methods. Numerical experiments demonstrate the practical effectiveness of the proposed methods for a model problem.