Linearized factorization techniques for multidimensional reaction—diffusion equations

An iterative predictor—corrector technique for the elimination of the approximate factorization errors which result from the factorization of linearized θ-methods in multidimensional reaction—diffusion equations is proposed, and its convergence and linear stability are analyzed. Four approximate factorization techniques which do not account for the approximate factorization errors are developed. The first technique uses the full Jacobian matrix of the reaction terms, requires the inversion of, in general, dense matrices, and its approximate factorization errors are second-order accurate in time. The second and third methods approximate the Jacobian matrix by diagonal or triangular ones which are easily inverted but their approximate factorization errors are, however, first-order accurate in time. The fourth approximately factorized method has approximate factorization errors which are second-order accurate in time and requires the inversion of lower and upper triangular matrices. The techniques are applied to a nonlinear, two-species, two-dimensional system of reaction—diffusion equations in order to determine the approximate factorization errors and those resulting from the approximations to the Jacobian matrix as functions of the allocation of the reaction terms, space and time.     

Bezoutian矩阵的一致逼近形式

借助闭区间上的连续函数可以用Bernstein 多项式一致逼近这一事实,将多项式对所生成的经典Bezoutian 矩阵和Bernstein Bezoutian 矩阵推广到C [0,1]上函数对所对应的情形,给出了 Bezoutian 矩阵一致逼近形式的定义,并且得到如下结论：给出了经典 Bezoutian 矩阵的 Barnett 型分解公式和三角分解公式的一致逼近形式;提供了经典Bezoutian 矩阵和Bernstein Bezoutian 矩阵的一致逼近形式的两类算法;得到了上述两种矩阵的一致逼近形式中元素间的两个恒等关系式。最后,利用数值实例对恒等关系式进行验证,结果表明两类算法是有效的。     

Combination of numerical and structured approaches to the construction of a second-order incomplete triangular factorization in parallel preconditioning methods

Parallel versions of the stabilized second-order incomplete triangular factorization conjugate gradient method in which the reordering of the coefficient matrix corresponding to the ordering based on splitting into subdomains with separators are considered. The incomplete triangular factorization is organized using the truncation of fill-in “by value” at internal nodes of subdomains, and “by value” and ‘by positions” on the separators. This approach is generalized for the case of constructing a parallel version of preconditioning the second-order incomplete LU factorization for nonsymmetric diagonally dominant matrices with. The reliability and convergence rate of the proposed parallel methods is analyzed. The proposed algorithms are implemented using MPI, results of solving benchmark problems with matrices from the collection of the University of Florida are presented.     

Incremental Norm Estimation for Dense and Sparse Matrices

We present an incremental approach to 2-norm estimation for triangular matrices. Our investigation covers both dense and sparse matrices which can arise for example from a QR, a Cholesky or a LU factorization. If the explicit inverse of a triangular factor is available, as in the case of an implicit version of the LU factorization, we can relate our results to incremental condition estimation (ICE). Incremental norm estimation (INE) extends directly from the dense to the sparse case without needing the modifications that are necessary for the sparse version of ICE. INE can be applied to complement ICE, since the product of the two estimates gives an estimate for the matrix condition number. Furthermore, when applied to matrix inverses, INE can be used as the basis of a rank-revealing factorization.     

Wiener-Hopf factorization for a class of oscillatory symbols

Two classes of 2×2 matrix symbols involving oscillatory functions are considered, one of which consists of triangular matrices. An equivalence theorem is obtained, concerning the solution of Riemann-Hilbert problems associated with each of them. Conditions for existence of canonical generalized factorization are established, as well as boundedness conditions for the factors. Explicit formulas are derived for the factors, showing in particular that only one of the columns needs to be calculated. The results are applied to solving a corona problem.     

范德蒙型方程组最小二乘解的快速算法

在用多项式进行曲线拟合等实际问题中,需要求解以范德蒙型矩阵VT为系数阵的线性方程组VTx=b的最小二乘解.     

两类下三角形Pascal矩阵的相似性

本文研究了Pascal矩阵与位移Pascal矩阵之间的关系.利用组合恒等式与矩阵分解的方法,得到了Pascal矩阵以及位移Pascal矩阵与若当标准型之间的过渡矩阵.同时也得到了这两类矩阵在域Zp上的最小多项式.     

Toeplitz型矩阵的逆矩阵的快速三角分解算法

针对有关“型”矩阵的三角分解问题 ,提出了一种 Toeplitz型矩阵的逆矩阵的快速三角分解算法 .首先假设给定 n阶非奇异矩阵 A,利用一组线性方程组的解 ,得到 A- 1的一个递推关系式 ,进而利用该关系式得到 A- 1的一种三角分解表达式 ,然后从 Toeplitz型矩阵的特殊结构出发 ,利用上述定理的结论 ,给出了Toeplitz型矩阵的逆矩阵的一种快速三角分解算法 ,算法所需运算量为 O( mn2 ) .最后 ,数值计算表明该算法的可靠性 .     

Fast solution of unsymmetric banded Toeplitz systems by means of spectral factorizations and Woodbury's formula

A fast algorithm for solving systems of linear equations with banded Toeplitz matrices is studied. An important step in the algorithm is a novel method for the spectral factorization of the generating function associated with the Toeplitz matrix. The spectral factorization is extracted from the right deflating subspaces corresponding to the eigenvalues inside and outside the open unit disk of a companion matrix pencil constructed from the coefficients of the generating function. The factorization is followed by the Woodbury inversion formula and solution of several banded triangular systems. Stability of the algorithm is discussed and its performance is demonstrated by numerical experiments. Copyright © 2012 John Wiley & Sons, Ltd.     

Block LU factorizations of M–matrices

Summary. It is well known that any nonsingular M–matrix admits an LU factorization into M–matrices (with L and U lower and upper triangular respectively) and any singular M–matrix is permutation similar to an M–matrix which admits an LU factorization into M–matrices. Varga and Cai establish necessary and sufficient conditions for a singular M–matrix (without permutation) to allow an LU factorization with L nonsingular. We generalize these results in two directions. First, we find necessary and sufficient conditions for the existence of an LU factorization of a singular M-matrix where L and U are both permitted to be singular. Second, we establish the minimal block structure that a block LU factorization of a singular M–matrix can have when L and U are M–matrices. Received November 21, 1994 / Revised version received August 4, 1997     

Factorizations of Cauchy matrices

The development of fast algorithms for the solution of linear systems of equations with a Cauchy matrix has recently received considerable attention. Several of these algorithms factor a Cauchy matrix or its inverse into triangular and possibly diagonal matrices. The numerical properties of the factorization methods depend on the selection of pivots. This note presents elementary derivations of some factorization methods and describes a new strategy for searching both rows and columns for suitable pivots.     

A backward stability analysis of diagonal pivoting methods for solving unsymmetric tridiagonal systems without interchanges

This paper concerns the LBM ^T factorization of unsymmetric tridiagonal matrices, where L and M are unit lower triangular matrices and B is block diagonal with 1×1 and 2×2 blocks. In some applications, it is necessary to form this factorization without row or column interchanges while the tridiagonal matrix is formed. Bunch and Kaufman proposed a pivoting strategy without interchanges specifically for symmetric tridiagonal matrices, and more recently, Bunch and Marcia proposed pivoting strategies that are normwise backward stable for linear systems involving such matrices. In this paper, we extend these strategies to the unsymmetric tridiagonal case and demonstrate that the proposed methods both exhibit bounded growth factors and are normwise backward stable. Copyright © 2009 John Wiley & Sons, Ltd.     

Multiple LU factorizations of a singular matrix

A singular matrix A may have more than one LU factorizations. In this work the set of all LU factorizations of A is explicitly described when the lower triangular matrix L is nonsingular. To this purpose, a canonical form of A under left multiplication by unit lower triangular matrices is introduced. This canonical form allows us to characterize the matrices that have an LU factorization and to parametrize all possible LU factorizations. Formulae in terms of quotient of minors of A are presented for the entries of this canonical form.     

r-对称循环矩阵及逆矩阵三角分解的快速算法

根据r-对称循环矩阵的特殊结构给出了求这类矩阵本身及其逆矩阵三角分解的快速算法,算法的运算量均为O(n2),一般矩阵及逆矩阵三角分解的运算量均为O(n3).     

Polynomial functions on upper triangular matrix algebras

There are two kinds of polynomial functions on matrix algebras over commutative rings: those induced by polynomials with coefficients in the algebra itself and those induced by polynomials with scalar coefficients. In the case of algebras of upper triangular matrices over a commutative ring, we characterize the former in terms of the latter (which are easier to handle because of substitution homomorphism). We conclude that the set of integer-valued polynomials with matrix coefficients on an algebra of upper triangular matrices is a ring, and that the set of null-polynomials with matrix coefficients on an algebra of upper triangular matrices is an ideal.     

六类不确定型判断矩阵的相容性研究

介绍区间数互补判断矩阵、区间数互反判断矩阵、区间数混合判断矩阵、三角模糊数互补判断矩阵、三角模糊数互反判断矩阵和三角模糊数混合判断矩阵等概念，给出衡量六类不确定型判断矩阵(区间数互补判断矩阵、区间数互反判断矩阵、区间数混合判断矩阵、三角模糊数互补判断矩阵、三角模糊数互反判断矩阵以及三角模糊数混合判断矩阵)同类型之间相容性的两个通用指标，并给出上述六类不确定型判断矩阵相容性的度量准则，最后进行算例分析。     

Semiscalar equivalence and the factorization of polynomial matrices

One considers the problem of the factorization of polynomial matrices over an arbitrary field in connection with their reducibility by semiscalar equivalent transformations to triangular form with the invariant factors along the principal diagonal. In particular, one establishes a criterion for the representability of a polynomial matrix in the form of a product of factors (the first of which is unital), the product of the canonical diagonal forms of which is equal to the canonical diagonal form of the given matrix. There is given also a method for the construction of such factorizations.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 42, No. 5, pp. 644–649, May, 1990.     

Analysis of incomplete factorizations for a nine-point approximation to a convection–diffusion model problem

We study the stability of zero-fill incomplete LU factorizations of a nine-point coefficient matrix arising from a high-order compact discretisation of a two-dimensional constant-coefficient convection–diffusion problem. Nonlinear recurrences for computing entries of the lower and upper triangular matrices are derived and we show that the sequence of diagonal entries of the lower triangular factor is unconditionally convergent. A theoretical estimate of the limiting value is derived and we show that this estimate is a good predictor of the computed value. The unconditional convergence of the diagonal sequence of the lower triangular factor to a positive limit implies that the incomplete factorization process never encounters a zero pivot and that the other diagonal sequences are also convergent. The characteristic polynomials associated with the lower and upper triangular solves that occur during the preconditioning step are studied and conditions for the stability of the triangular solves are derived in terms of the entries of the tridiagonal matrices appearing in the lower and upper subdiagonals of the block triangular system matrix and a triplet of parameters which completely determines the solution of the nonlinear recursions. Results of ILU-preconditioned GMRES iterations and the effects of orderings on their convergence are also described.     

Cauchy型矩阵及其逆矩阵的快速三角分解

Abstract, In this paper,algorithms for determining the triangular factorization of Cauchy typematrices and their inverses are derived by using O(n2) operations.     

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.