Extending the notions of companion and infinite companion to matrix polynomials

The notion of infinite companion matrix is extended to the case of matrix polynomials (including polynomials with singular leading coefficient). For row reduced polynomials a finite companion is introduced as the compression of the shift matrix. The methods are based on ideas of dilation theory. Connections with systems theory are indicated. Applications to the problem of linearization of matrix polynomials, solution of systems of difference and differential equations and new factorization formulae for infinite block Hankel matrices having finite rank are shown. As a consequence, any system of linear difference or differential equations with constant coefficients can be transformed into a first order system of dimension n = deg det D.     

Preconditioning and iterative solution of symmetric indefinite linear systems arising from interior point methods for linear programming

We propose to compute the search direction at each interior-point iteration for a linear program via a reduced augmented system that typically has a much smaller dimension than the original augmented system. This reduced system is potentially less susceptible to the ill-conditioning effect of the elements in the (1,1) block of the augmented matrix. A preconditioner is then designed by approximating the block structure of the inverse of the transformed matrix to further improve the spectral properties of the transformed system. The resulting preconditioned system is likely to become better conditioned toward the end of the interior-point algorithm. Capitalizing on the special spectral properties of the transformed matrix, we further proposed a two-phase iterative algorithm that starts by solving the normal equations with PCG in each IPM iteration, and then switches to solve the preconditioned reduced augmented system with symmetric quasi-minimal residual (SQMR) method when it is advantageous to do so. The experimental results have demonstrated that our proposed method is competitive with direct methods in solving large-scale LP problems and a set of highly degenerate LP problems. Research supported in parts by NUS Research Grant R146-000-076-112 and SMA IUP Research Grant.     

A direct method for solving block‐Toeplitz with near‐circulant‐block systems with applications to hybrid manufacturing systems

In this paper, we present a direct method for solving linear systems of a block‐Toeplitz matrix with each block being a near‐circulant matrix. The direct method is based on the fast Fourier transform (FFT) and the Sherman–Morrison–Woodbury formula. We give a cost analysis for the proposed method. The method is then applied to solve the steady‐state probability distribution of a hybrid manufacturing system which consists of a manufacturing process and a re‐manufacturing process. Copyright © 2005 John Wiley & Sons, Ltd.     

Efficient and stable solution of structured Hessenberg linear systems arising from difference equations

This paper is concerned with the efficient solution of (block) Hessenberg linear systems whose coefficient matrix is a Toeplitz matrix in (block) Hessenberg form plus a band matrix. Such problems arise, for instance, when we apply a computational scheme based on the use of difference equations for the computation of many significant special functions and quantities occurring in engineering and physics. We present a divide‐and‐conquer algorithm that combines some recent techniques for the numerical treatment of structured Hessenberg linear systems. Our approach is computationally efficient and, moreover, in many practical cases it can be shown to be componentwise stable. Copyright © 2000 John Wiley & Sons, Ltd.     

Parallel iterative solvers for boundary value methods

A parallel variant of the block Gauss-Seidel iteration for the solution of block-banded linear systems is presented. The coefficient matrix is partitioned among the processors as in the domain decomposition methods and then it is split so that the resulting iterative method has the same spectral properties of the block Gauss-Seidel iteration.The parallel algorithm is applied to the solution of block-banded linear systems arising from the numerical discretization of initial value problems by means of Boundary Value Methods (BVMs). BVMs define a new approach for the solution of ordinary differential equations and seem to be attractive for their interesting stability properties and a possible parallel implementation. In this paper, we refer to BVMs based on the extended trapezoidal rules.     

Block and joint ℋ︁-matrix preconditioners for the Oseen equations

For saddle point problems in fluid dynamics, many preconditioners in the literature exploit the block structure of the problem to construct block diagonal or block triangular preconditioners. The performance of such preconditioners depends on whether fast, approximate solvers for the linear systems on the block diagonal as well as for the Schur complement are available. We will construct these efficient preconditioners using hierarchical matrix techniques in which fully populated matrices are approximated by blockwise low rank approximations. We will compare such block preconditioners with those obtained through a completely different approach where the given block structure is not used but a domain-decomposition based ℋ︁-LU factorization is constructed for the complete system matrix. Preconditioners resulting from these two approaches will be discussed and compared through numerical results. (© 2006 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

求解具有张量积结构线性系统的共轭梯度法

本文考虑具有张量积结构线性系统的数值解法．该线性系统常常来源于高维立方体上线性偏微分方程的有限差分离散化．利用张量一矩阵乘法,给出了基于张量格式的求解这类线性系统的共轭梯度法．与求解标准线性系统的共轭梯度法比较,新的算法能够节约大量的计算量及存储空间．     

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.     

A deflated conjugate gradient method for multiple right hand sides and multiple shifts

We consider the task of computing solutions of linear systems that only differ by a shift with the identity matrix as well as linear systems with several different right-hand sides. In the past, Krylov subspace methods have been developed which exploit either the need for solutions to multiple right-hand sides (e.g. deflation type methods and block methods) or multiple shifts (e.g. shifted CG) with some success. In this paper we present a block Krylov subspace method which, based on a block Lanczos process, exploits both features—shifts and multiple right-hand sides—at once. Such situations arise, for example, in lattice quantum chromodynamics (QCD) simulations within the Rational Hybrid Monte Carlo (RHMC) algorithm. We present numerical evidence that our method is superior compared to applying other iterative methods to each of the systems individually as well as, in typical situations, to shifted or block Krylov subspace methods.     

求解一类分块二阶线性方程组的QHSS迭代方法

本文将QHSS迭代方法运用于求解一类分块二阶线性方程组.通过适当地放宽QHSS迭代方法的收敛性条件,我们给出了用QHSS迭代方法求解一类分块二阶线性方程组的具体迭代格式,并证明了当系数矩阵中的(1,1)块对称半正定时该QHSS迭代方法的收敛性.我们还用数值实验验证了QHSS迭代方法的可行性和有效性.     

三阶线性常微分方程Sinc方程组的结构预处理方法

三阶线性常微分方程在天文学和流体力学等学科的研究中有着广泛的应用.本文介绍求解三阶线性常微分方程由Sinc方法离散所得到的线性方程组的结构预处理方法.首先, 我们利用Sinc方法对三阶线性常微分方程进行离散,证明了离散解以指数阶收敛到原问题的精确解.针对离散后线性方程组的系数矩阵的特殊结构, 提出了结构化的带状预处理子,并证明了预处理矩阵的特征值位于复平面上的一个矩形区域之内.然后, 我们引入新的变量将三阶线性常微分方程等价地转化为由两个二阶线性常微分方程构成的常微分方程组, 并利用Sinc方法对降阶后的常微分方程组进行离散.离散后线性方程组的系数矩阵是分块2×2的, 且每一块都是Toeplitz矩阵与对角矩阵的组合.为了利用Krylov子空间方法有效地求解离散后的线性方程组,我们给出了块对角预处理子, 并分析了预处理矩阵的性质.最后, 我们对降阶后二阶线性常微分方程组进行了一些比较研究.数值结果证实了Sinc方法能够有效地求解三阶线性常微分方程.     

Efficient Kansa-type MFS algorithm for elliptic problems

In this study we propose an efficient Kansa-type method of fundamental solutions (MFS-K) for the numerical solution of certain problems in circular geometries. In particular, we consider problems governed by the inhomogeneous Helmholtz equation in disks and annuli. The coefficient matrices in the linear systems resulting from the MFS-K discretization of these problems possess a block circulant structure and can thus be solved by means of a matrix decomposition algorithm and fast Fourier Transforms. Several numerical examples demonstrating the efficacy of the proposed algorithm are presented.     

Skew-symmetric methods for nonsymmetric linear systems with multiple right-hand sides

By transforming nonsymmetric linear systems to the extended skew-symmetric ones, we present the skew-symmetric methods for solving nonsymmetric linear systems with multiple right-hand sides. These methods are based on the block and global Arnoldi algorithm which is formed by implementing orthogonal projections of the initial matrix residual onto a matrix Krylov subspace. The algorithms avoid the tediously long Arnoldi process and highly reduce expensive storage. Numerical experiments show that these algorithms are effective and give better practical performances than global GMRES for solving nonsymmetric linear systems with multiple right-hand sides.     

Theorems on Schur complement of block diagonally dominant matrices and their application in reducing the order for the solution of large scale linear systems

We firstly consider the block dominant degree for I-(II-)block strictly diagonally dominant matrix and their Schur complements, showing that the block dominant degree for the Schur complement of an I-(II-)block strictly diagonally dominant matrix is greater than that of the original grand block matrix. Then, as application, we present some disc theorems and some bounds for the eigenvalues of the Schur complement by the elements of the original matrix. Further, by means of matrix partition and the Schur complement of block matrix, based on the derived disc theorems, we give a kind of iteration called the Schur-based iteration, which can solve large scale linear systems though reducing the order by the Schur complement and the numerical example illustrates that the iteration can compute out the results faster.     

A splitting preconditioner for implicit Runge-Kutta discretizations of a partial differential-algebraic equation

In this paper we study efficient iterative methods for solving the system of linear equations arising from the fully implicit Runge-Kutta discretizations of a class of partial differential-algebraic equations. In each step of the time integration, a block two-by-two linear system is obtained and needed to be solved numerically. A preconditioning strategy based on an alternating Kronecker product splitting of the coefficient matrix is proposed to solve such linear systems. Some spectral properties of the preconditioned matrix are established and numerical examples are presented to demonstrate the effectiveness of this approach.     

A real-valued block conjugate gradient type method for solving complex symmetric linear systems with multiple right-hand sides

We consider solving complex symmetric linear systems with multiple right-hand sides. We assume that the coefficient matrix has indefinite real part and positive definite imaginary part. We propose a new block conjugate gradient type method based on the Schur complement of a certain 2-by-2 real block form. The algorithm of the proposed method consists of building blocks that involve only real arithmetic with real symmetric matrices of the original size. We also present the convergence property of the proposed method and an efficient algorithmic implementation. In numerical experiments, we compare our method to a complex-valued direct solver, and a preconditioned and nonpreconditioned block Krylov method that uses complex arithmetic.     

Block two-stage preconditioners

Linear systems of the form Ax = b, where the matrix A is symmetric and positive definite, often arise from the discretization of elliptic partial differential equations. A very successful method for solving these linear systems is the preconditioned conjugate gradient method. In this paper, we study parallel preconditioners for the conjugate gradient method based on the block two-stage iterative methods. Sufficient conditions for the validity of these preconditioners are given. Computational results of these preconditioned conjugate gradient methods on two parallel computing systems are presented.     

Block Two-stage Methods for Singular Systems and Markov Chains

The use of block two-stage methods for the iterative solution of consistent singular linear systems is studied. In these methods, suitable for parallel computations, different blocks, i.e., smaller linear systems, can be solved concurrently by different processors. Each of these smaller systems are solved by an (inner) iterative method. Hypotheses are provided for the convergence of non-stationary methods, i.e., when the number of inner iterations may vary from block to block and from one outer iteration to another. It is shown that the iteration matrix corresponding to one step of the block method is convergent, i.e., that its powers converge to a limit matrix. A theorem on the convergence of the infinite product of matrices with the same eigenspace corresponding to the eigenvalue 1 is proved, and later used as a tool in the convergence analysis of the block method. The methods studied can be used to solve any consistent singular system, including discretizations of certain differential equations. They can also be used to find stationary probability distribution of Markov chains. This last application is considered in detail.     

A method for verifying the accuracy of numerical solutions of symmetric saddle point linear systems

A fast numerical verification method is proposed for evaluating the accuracy of numerical solutions for symmetric saddle point linear systems whose diagonal blocks of the coefficient matrix are semidefinite matrices. The method is based on results of an algebraic analysis of a block diagonal preconditioning. Some numerical experiments are present to illustrate the usefulness of the method.     

A preconditioner for generalized saddle point problems: Application to 3D stationary Navier‐Stokes equations

In this article we consider the stationary Navier‐Stokes system discretized by finite element methods which do not satisfy the inf‐sup condition. These discretizations typically take the form of a variational problem with stabilization terms. Such a problem may be transformed by iteration methods into a sequence of linear, Oseen‐type variational problems. On the algebraic level, these problems belong to a certain class of linear systems with nonsymmetric system matrices (“generalized saddle point problems”). We show that if the underlying finite element spaces satisfy a generalized inf‐sup condition, these problems have a unique solution. Moreover, we introduce a block triangular preconditioner and we show how the eigenvalue bounds of the preconditioned system matrix depend on the coercivity constant and continuity bounds of the bilinear forms arising in the variational problem. Finally we prove that the stabilized P1‐P1 finite element method proposed by Rebollo is covered by our theory and we show that the condition number of the preconditioned system matrix is independent of the mesh size. Numerical tests with 3D stationary Navier‐Stokes flows confirm our results. © 2006 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 2006