Factorization strategies for third-order tensors

Operations with tensors, or multiway arrays, have become increasingly prevalent in recent years. Traditionally, tensors are represented or decomposed as a sum of rank-1 outer products using either the CANDECOMP/PARAFAC (CP) or the Tucker models, or some variation thereof. Such decompositions are motivated by specific applications where the goal is to find an approximate such representation for a given multiway array. The specifics of the approximate representation (such as how many terms to use in the sum, orthogonality constraints, etc.) depend on the application.In this paper, we explore an alternate representation of tensors which shows promise with respect to the tensor approximation problem. Reminiscent of matrix factorizations, we present a new factorization of a tensor as a product of tensors. To derive the new factorization, we define a closed multiplication operation between tensors. A major motivation for considering this new type of tensor multiplication is to devise new types of factorizations for tensors which can then be used in applications.Specifically, this new multiplication allows us to introduce concepts such as tensor transpose, inverse, and identity, which lead to the notion of an orthogonal tensor. The multiplication also gives rise to a linear operator, and the null space of the resulting operator is identified. We extend the concept of outer products of vectors to outer products of matrices. All derivations are presented for third-order tensors. However, they can be easily extended to the order-p(p>3) case. We conclude with an application in image deblurring.     

Data-sparse approximation to a class of operator-valued functions

In earlier papers we developed a method for the data-sparse approximation of the solution operators for elliptic, parabolic, and hyperbolic PDEs based on the Dunford-Cauchy representation to the operator-valued functions of interest combined with the hierarchical matrix approximation of the operator resolvents. In the present paper, we discuss how these techniques can be applied to approximate a hierarchy of the operator-valued functions generated by an elliptic operator .

     

Convergence of block iterative methods for linear systems with generalized H-matrices

The paper studies the convergence of some block iterative methods for the solution of linear systems when the coefficient matrices are generalized H$H$-matrices. A truth is found that the class of conjugate generalized H$H$-matrices is a subclass of the class of generalized H$H$-matrices and the convergence results of R. Nabben [R. Nabben, On a class of matrices which arises in the numerical solution of Euler equations, Numer. Math. 63 (1992) 411–431] are then extended to the class of generalized H$H$-matrices. Furthermore, the convergence of the block AOR iterative method for linear systems with generalized H$H$-matrices is established and some properties of special block tridiagonal matrices arising in the numerical solution of Euler equations are discussed. Finally, some examples are given to demonstrate the convergence results obtained in this paper.     

The best circulant preconditioners for Hermitian Toeplitz systems II: The multiple-zero case

Summary. In [10,14], circulant-type preconditioners have been proposed for ill-conditioned Hermitian Toeplitz systems that are generated by nonnegative continuous functions with a zero of even order. The proposed circulant preconditioners can be constructed without requiring explicit knowledge of the generating functions. It was shown that the spectra of the preconditioned matrices are uniformly bounded except for a fixed number of outliers and that all eigenvalues are uniformly bounded away from zero. Therefore the conjugate gradient method converges linearly when applied to solving the circulant preconditioned systems. In [10,14], it was claimed that this result can be the case where the generating functions have multiple zeros. The main aim of this paper is to give a complete convergence proof of the method in [10,14] for this class of generating functions. Received October 19, 1999 / Revised version received May 2, 2001 / Published online October 17, 2001     

Convergence analysis of two-grid methods for elliptic Toeplitz and PDEs Matrix-sequences

Summary. The solution of large Toeplitz systems with nonnegative generating functions by multigrid methods was proposed in previous papers [13,14,22]. The technique was modified in [6,36] and a rigorous proof of convergence of the TGM (two-grid method) was given in the special case where the generating function has only a zero at of order at most two. Here, by extending the latter approach, we perform a complete analysis of convergence of the TGM under the sole assumption that f is nonnegative and with a zero at of finite order. An extension of the same analysis in the multilevel case and in the case of finite difference matrix sequences discretizing elliptic PDEs with nonconstant coefficients and of any order is then discussed. Received May 28, 1999 / Revised version received January 26, 2001 / Published online November 15, 2001     

Pivoting strategies leading to diagonal dominance by rows

Pivoting strategies for Gaussian elimination leading to upper triangular matrices which are diagonally dominant by rows are studied. Forward error analysis of triangular systems whose coefficient matrices are diagonally dominant by rows is performed. We also obtain small bounds of the backward errors for the pivoting strategies mentioned above. Our examples of matrices include H-matrices and some generalizations of diagonally dominant matrices, and scaled partial pivoting for the 1-norm is an example of these pivoting strategies. In the case of an M-matrix, a pivoting strategy of computational complexity is proposed, which satisfies all the results of the paper. Received June 6, 1997 / Revised version received October 27, 1997     

Preconditioning cubic spline collocation discretizations of elliptic equations

Summary. This work considers the uniformly elliptic operator defined by in (the unit square) with boundary conditions: on and on and its discretization based on Hermite cubic spline spaces and collocation at the Gauss points. Using an interpolatory basis with support on the Gauss points one obtains the matrix . We discuss the condition numbers and the distribution of -singular values of the preconditioned matrices where is the stiffness matrix associated with the finite element discretization of the positive definite uniformly elliptic operator given by in with boundary conditions: on on . The finite element space is either the space of continuous functions which are bilinear on the rectangles determined by Gauss points or the space of continuous functions which are linear on the triangles of the triangulation of using the Gauss points. When we obtain results on the eigenvalues of . In the general case we obtain bounds and clustering results on the -singular values of . These results are related to the results of Manteuffel and Parter [MP], Parter and Wong [PW], and Wong [W] for finite element discretizations as well as the results of Parter and Rothman [PR] for discretizations based on Legendre Spectral Collocation. Received January 1, 1994 / Revised version received February 7, 1995     

Some properties of generalized K-centrosymmetric H-matrices

Every n×n$n\times n$ generalized K-centrosymmetric matrix A   can be reduced into a 2×2$2\times 2$ block diagonal matrix (see [Z. Liu, H. Cao, H. Chen, A note on computing matrix–vector products with generalized centrosymmetric (centrohermitian) matrices, Appl. Math. Comput. 169 (2) (2005) 1332–1345]). This block diagonal matrix is called the reduced form of the matrix A. In this paper we further investigate some properties of the reduced form of these matrices and discuss the square roots of these matrices. Finally exploiting these properties, the development of structure-preserving algorithms for certain computations for generalized K-centrosymmetric H-matrices is discussed.     

Domain decomposition based $${\mathcal H}$$ -LU preconditioning

Hierarchical matrices provide a data-sparse way to approximate fully populated matrices. The two basic steps in the construction of an -matrix are (a) the hierarchical construction of a matrix block partition, and (b) the blockwise approximation of matrix data by low rank matrices. In this paper, we develop a new approach to construct the necessary partition based on domain decomposition. Compared to standard geometric bisection based -matrices, this new approach yields -LU factorizations of finite element stiffness matrices with significantly improved storage and computational complexity requirements. These rigorously proven and numerically verified improvements result from an -matrix block structure which is naturally suited for parallelization and in which large subblocks of the stiffness matrix remain zero in an LU factorization. We provide numerical results in which a domain decomposition based -LU factorization is used as a preconditioner in the iterative solution of the discrete (three-dimensional) convection-diffusion equation. This work was supported in part by the US Department of Energy under Grant No. DE-FG02-04ER25649 and by the National Science Foundation under grant No. DMS-0408950.     

Note on structured indefinite perturbations to Hermitian matrices

In a recent paper, Overton and Van Dooren have considered structured indefinite perturbations to a given Hermitian matrix. We extend their results to skew-Hermitian, Hamiltonian and skew-Hamiltonian matrices. As an application, we give a formula for computation of the smallest perturbation with a special structure, which makes a given Hamiltonian matrix own a purely imaginary eigenvalue.     

Computing multiple integrals involving matrix exponentials

In this paper, a generalization of a formula proposed by Van Loan [Computing integrals involving the matrix exponential, IEEE Trans. Automat. Control 23 (1978) 395–404] for the computation of multiple integrals of exponential matrices is introduced. In this way, the numerical evaluation of such integrals is reduced to the use of a conventional algorithm to compute matrix exponentials. The formula is applied for evaluating some kinds of integrals that frequently emerge in a number classical mathematical subjects in the framework of differential equations, numerical methods and control engineering applications.     

Finite difference preconditioning cubic spline collocation method of elliptic equations

Summary. We discuss a finite difference preconditioner for the interpolatory cubic spline collocation method for a uniformly elliptic operator defined by in (the unit square) with homogeneous Dirichlet boundary conditions. Using the generalized field of values arguments, we discuss the eigenvalues of the preconditioned matrix where is the matrix of the collocation discretization operator corresponding to , and is the matrix of the finite difference operator corresponding to the uniformly elliptic operator given by in with homogeneous Dirichlet boundary conditions. Finally we mention a bound of -singular values of for a general elliptic operator in . Received December 11, 1995 / Revised version received June 20, 1996     

Backward errors for eigenproblem of two kinds of structured matrices

In this paper, we consider backward errors in the eigenproblem of symmetric centrosymmetric and symmetric skew-centrosymmetric matrices. By making use of the properties of symmetric centrosymmetric and symmetric skew-centrosymmetric matrices, we derive explicit formulae for the backward errors of approximate eigenpairs.     

On the inverses of general tridiagonal matrices

In this work, the sign distribution for all inverse elements of general tridiagonal H-matrices is presented. In addition, some computable upper and lower bounds for the entries of the inverses of diagonally dominant tridiagonal matrices are obtained. Based on the sign distribution, these bounds greatly improve some well-known results due to Ostrowski (1952) 23, Shivakumar and Ji (1996) 26, Nabben (1999) [21] and [22] and recently given by Peluso and Politi (2001) 24, Peluso and Popolizio (2008) 25 and so forth. It is also stated that the inverse of a general tridiagonal matrix may be described by 2n-2 parameters ( and ) instead of 2n+2 ones as given by El-Mikkawy (2004) 3, El-Mikkawy and Karawia (2006) 4 and Huang and McColl (1997) 10. According to these results, a new symbolic algorithm for finding the inverse of a tridiagonal matrix without imposing any restrictive conditions is presented, which improves some recent results. Finally, several applications to the preconditioning technology, the numerical solution of differential equations and the birth-death processes together with numerical tests are given.     

On the modification of an eigenvalue problem that preserves an eigenspace

Eigenvalue problems arise in many application areas ranging from computational fluid dynamics to information retrieval. In these fields we are often interested in only a few eigenvalues and corresponding eigenvectors of a sparse matrix. In this paper, we comment on the modifications of the eigenvalue problem that can simplify the computation of those eigenpairs. These transformations allow us to avoid difficulties associated with non-Hermitian eigenvalue problems, such as the lack of reliable non-Hermitian eigenvalue solvers, by mapping them into generalized Hermitian eigenvalue problems. Also, they allow us to expose and explore parallelism. They require knowledge of a selected eigenvalue and preserve its eigenspace. The positive definiteness of the Hermitian part is inherited by the matrices in the generalized Hermitian eigenvalue problem. The position of the selected eigenspace in the ordering of the eigenvalues is also preserved under certain conditions. The effect of using approximate eigenvalues in the transformation is analyzed and numerical experiments are presented.     

Characterizations of inverse M-matrices with special zero patterns

In this paper, we provide some characterizations of inverse M-matrices with special zero patterns. In particular, we give necessary and sufficient conditions for k-diagonal matrices and symmetric k-diagonal matrices to be inverse M-matrices. In addition, results for triadic matrices, tridiagonal matrices and symmetric 5-diagonal matrices are presented as corollaries.     

Rate of Convergence for some constraint decomposition methods for nonlinear variational inequalities

Summary. Some general subspace correction algorithms are proposed for a convex optimization problem over a convex constraint subset. One of the nontrivial applications of the algorithms is the solving of some obstacle problems by multilevel domain decomposition and multigrid methods. For domain decomposition and multigrid methods, the rate of convergence for the algorithms for obstacle problems is of the same order as the rate of convergence for jump coefficient linear elliptic problems. In order to analyse the convergence rate, we need to decompose a finite element function into a sum of functions from the subspaces and also satisfying some constraints. A special nonlinear interpolation operator is introduced for decomposing the functions. Received December 13, 2001 / Revised version received February 19, 2002 / Published online June 17, 2002 This work was partially supported by the Norwegian Research Council under projects 128224/431 and SEP-115837/431.