On Euclidean distance matrices

If A is a real symmetric matrix and P is an orthogonal projection onto a hyperplane, then we derive a formula for the Moore-Penrose inverse of PAP. As an application, we obtain a formula for the Moore-Penrose inverse of an Euclidean distance matrix (EDM) which generalizes formulae for the inverse of a EDM in the literature. To an invertible spherical EDM, we associate a Laplacian matrix (which we define as a positive semidefinite n × n matrix of rank n − 1 and with zero row sums) and prove some properties. Known results for distance matrices of trees are derived as special cases. In particular, we obtain a formula due to Graham and Lovász for the inverse of the distance matrix of a tree. It is shown that if D is a nonsingular EDM and L is the associated Laplacian, then D⁻¹ − L is nonsingular and has a nonnegative inverse. Finally, infinitely divisible matrices are constructed using EDMs.     

Taussky定理推广与应用

本文在Ｃａｓｓｉｎｉ卵形域上推广了Ｔａｕｓｓｋｙ定理。所得结果修正了Ｂｒａｕｅｒ定理,作为应用给出不可约双对角占优矩阵非奇异的充要条件,最后把基本结果推广到分块矩阵上。     

On parametrization of totally nonpositive matrices and applications

The problem of accurate computations for totally non‐negative matrices has been studied; however, it remains open for other sign regular matrices. One major obstacle is that there is no known parametrization of these matrices. The main contribution of the present work is that we provide such parametrization of nonsingular totally nonpositive matrices. A useful application of our results is that these parameters can determine accurately the entries of the inverse of a nonsingular totally nonpositive matrix. Copyright © 2011 John Wiley & Sons, Ltd.     

A multiwave approximate Riemann solver for ideal MHD based on relaxation II: numerical implementation with 3 and 5 waves

In the first part of this work Bouchut et al. (J Comput Phys 108:7–41, 2007) we introduced an approximate Riemann solver for one-dimensional ideal MHD derived from a relaxation system. We gave sufficient conditions for the solver to satisfy discrete entropy inequalities, and to preserve positivity of density and internal energy. In this paper we consider the practical implementation, and derive explicit wave speed estimates satisfying the stability conditions of Bouchut et al. (J Comput Phys 108:7–41, 2007). We present a 3-wave solver that well resolves fast waves and material contacts, and a 5-wave solver that accurately resolves the cases when two eigenvalues coincide. A full 7-wave solver, which is highly accurate on all types of waves, will be described in a follow-up paper. We test the solvers on one-dimensional shock tube data and smooth shear waves.     

Accurate computations of matrices with bidiagonal decomposition using methods for totally positive matrices

A class of sign‐symmetric P‐matrices including all nonsingular totally positive matrices and their inverses as well as tridiagonal nonsingular H‐matrices is presented and analyzed. These matrices present a bidiagonal decomposition that can be used to obtain algorithms to compute with high relative accuracy their singular values, eigenvalues, inverses, or their LDU factorization. Copyright © 2012 John Wiley & Sons, Ltd.     

Structural and computational properties of possibly singular semiseparable matrices

A classical result of structured numerical linear algebra states that the inverse of a nonsingular semiseparable matrix is a tridiagonal matrix. Such a property of a semiseparable matrix has been proved to be useful for devising linear complexity solvers, for establishing recurrence relations among its columns or rows and, moreover, for efficiently evaluating its characteristic polynomial. In this paper, we provide sparse structured representations of a semiseparable matrix A which hold independently of the fact that A is singular or not. These relations are found by pointing out the band structure of the inverse of the sum of A plus a certain sparse perturbation of minimal rank. Further, they can be used to determine in a computationally efficient way both a reflexive generalized inverse of A and its characteristic polynomial.     

A review of infinite matrices and their applications

Infinite matrices, the forerunner and a main constituent of many branches of classical mathematics (infinite quadratic forms, integral equations, differential equations, etc.) and of the modern operator theory, is revisited to demonstrate its deep influence on the development of many branches of mathematics, classical and modern, replete with applications. This review does not claim to be exhaustive, but attempts to present research by the authors in a variety of applications. These include the theory of infinite and related finite matrices, such as sections or truncations and their relationship to the linear operator theory on separable and sequence spaces. Matrices considered here have special structures like diagonal dominance, tridiagonal, sign distributions, etc. and are frequently nonsingular. Moreover, diagonally dominant finite and infinite matrices occur largely in numerical solutions of elliptic partial differential equations.The main focus is the theoretical and computational aspects concerning infinite linear algebraic and differential systems, using techniques like conformal mapping, iterations, truncations etc. to derive estimates based solutions. Particular attention is paid to computable precise error estimates, and explicit lower and upper bounds. Topics include Bessel’s, Mathieu equations, viscous fluid flow, simply and doubly connected regions, digital dynamics, eigenvalues of the Laplacian, etc. Also presented are results in generalized inverses and semi-infinite linear programming.     

A formula for computing (1,2,3)-inverses of g-circulants

Recent work on generalized inverses of linear operators centres around the construction of efficient algorithms for their computation. Here invariably structural properties of the operators and matrices involved are very convenient. As a contribution we obtain a rapidly evaluable explicit expression for (1, 2, 3)-inverses of singular g-circulants that originate in a nonsingular 1-circulant.     

广义严格对角占优矩阵与非奇M矩阵的判定

１引言Ｍ矩阵是计算数学中应给极其广泛的矩阵类,它出现于经济价值模型矩阵和反网络系统分析的系数矩阵及解某类确定微分方程问题的数值解法中．由于Ｍ矩阵的重要性,讨论Ｍ矩阵及相关的广义对角占优矩阵的判定及性质有着十分重要的意义．本文则是在文［１］～［３］基础上,给出了广义严格对角占优矩阵与非奇Ｍ矩阵几则新的充分条件．拓广了文［１］～［３］的相关结果．２主要结果定义１设Ａ＝（ａｉｊ）,如果存在正对角阵Ｄ,使得ＡＤ为严格对角占优阵,则称Ａ为广义严格对角占优阵．定义２设Ａ＝,Ｍ（Ａ）＝（Ｍｉｊ）,其中,则称Ｓ…     

Classes of general H-matrices

Let M(A) denote the comparison matrix of a square H-matrix A, that is, M(A) is an M-matrix. H-matrices such that their comparison matrices are nonsingular are well studied in the literature. In this paper, we study characterizations of H-matrices with either singular or nonsingular comparison matrices. The spectral radius of the Jacobi matrix of M(A) and the generalized diagonal dominance property are used in the characterizations. Finally, a classification of the set of general H-matrices is obtained.     

Parallel sparse linear algebra and application to structural mechanics

The framework of this paper is the parallelization of a plasticity algorithm that uses an implicit method and an incremental approach. More precisely, we will focus on some specific parallel sparse linear algebra algorithms which are the most time-consuming steps to solve efficiently such an engineering application. First, we present a general algorithm which computes an efficient static scheduling of block computations for parallel sparse linear factorization. The associated solver, based on a supernodal fan-in approach, is fully driven by this scheduling. Second, we describe a scalable parallel assembly algorithm based on a distribution of elements induced by the previous distribution for the blocks of the sparse matrix. We give an overview of these algorithms and present performance results on an IBM SP2 for a collection of grid and irregular problems. This revised version was published online in June 2006 with corrections to the Cover Date.     

Closed forms transverse to singular foliations

We describe a homological criterion for the existence of a closed form transverse to a foliation which is allowed to have certain tame singularities, generalizing results in the nonsingular case by Sullivan. As illustrations of the method, we derive results about the existence of singular symplectic forms and about the characterization of intrinsic harmonicity for forms.     

Nonsingular points on hypersurfaces over $ \mathbb{F}_q $

In this survey article, we investigate hypersurfaces defined over finite fields. More specifically, we determine for which hypersurfaces one can ensure the existence of a nonsingular point taking the cardinality of our ambient field large if need be. Additionally, for such hypersurfaces we will find a lower bound on the cardinality for which a nonsingular point is guaranteed.     

A multiwave approximate Riemann solver for ideal MHD based on relaxation. I: theoretical framework

We present a relaxation system for ideal magnetohydrodynamics (MHD) that is an extension of the Suliciu relaxation system for the Euler equations of gas dynamics. From it one can derive approximate Riemann solvers with three or seven waves, that generalize the HLLC solver for gas dynamics. Under some subcharacteristic conditions, the solvers satisfy discrete entropy inequalities, and preserve positivity of density and internal energy. The subcharacteristic conditions are nonlinear constraints on the relaxation parameters relating them to the initial states and the intermediate states of the approximate Riemann solver itself. The 7-wave version of the solver is able to resolve exactly all material and Alfven isolated contact discontinuities. Practical considerations and numerical results will be provided in another paper.     

Planar Conjugate Gradient Algorithm for Large-Scale Unconstrained Optimization,Part 1: Theory

In this paper, we present a new conjugate gradient (CG) based algorithm in the class of planar conjugate gradient methods. These methods aim at solving systems of linear equations whose coefficient matrix is indefinite and nonsingular. This is the case where the application of the standard CG algorithm by Hestenes and Stiefel (Ref. 1) may fail, due to a possible division by zero. We give a complete proof of global convergence for a new planar method endowed with a general structure; furthermore, we describe some important features of our planar algorithm, which will be used within the optimization framework of the companion paper (Part 2, Ref. 2). Here, preliminary numerical results are reported.This work was supported by MIUR, FIRB Research Program on Large-Scale Nonlinear Optimization, Rome, ItalyThe author acknowledges Luigi Grippo and Stefano Lucidi, who contributed considerably to the elaboration of this paper. The exchange of experiences with Massimo Roma was a constant help in the investigation. The author expresses his gratitude to the Associate Editor and the referees for suggestions and corrections.     

On the parallel GSAOR method for block diagonally dominant matrices

In this paper we consider the parallel generalized SAOR iterative method based on the generalized AOR iterative method presented by James for solving large nonsingular system. We obtain some convergence theorems for the case when coefficient matrix is a block diagonally dominant matrix or a generalized block diagonal dominant matrix. A numerical example is given to illustrate to our results.     

Powers of complex persymmetric or skew-persymmetric anti-tridiagonal matrices with constant anti-diagonals

In this paper, we derive a general expression for the entries of the powers of any complex persymmetric or skew-persymmetric anti-tridiagonal matrix with constant anti-diagonals, in terms of the Chebyshev polynomials of the second kind.     

A stable primal–dual approach for linear programming under nondegeneracy assumptions

This paper studies a primal–dual interior/exterior-point path-following approach for linear programming that is motivated on using an iterative solver rather than a direct solver for the search direction. We begin with the usual perturbed primal–dual optimality equations. Under nondegeneracy assumptions, this nonlinear system is well-posed, i.e. it has a nonsingular Jacobian at optimality and is not necessarily ill-conditioned as the iterates approach optimality. Assuming that a basis matrix (easily factorizable and well-conditioned) can be found, we apply a simple preprocessing step to eliminate both the primal and dual feasibility equations. This results in a single bilinear equation that maintains the well-posedness property. Sparsity is maintained. We then apply either a direct solution method or an iterative solver (within an inexact Newton framework) to solve this equation. Since the linearization is well posed, we use affine scaling and do not maintain nonnegativity once we are close enough to the optimum, i.e. we apply a change to a pure Newton step technique. In addition, we correctly identify some of the primal and dual variables that converge to 0 and delete them (purify step). We test our method with random nondegenerate problems and problems from the Netlib set, and we compare it with the standard Normal Equations NEQ approach. We use a heuristic to find the basis matrix. We show that our method is efficient for large, well-conditioned problems. It is slower than NEQ on ill-conditioned problems, but it yields higher accuracy solutions.     

A look-ahead algorithm for the solution of general Hankel systems

Summary The solution of systems of linear equations with Hankel coefficient matrices can be computed with onlyO(n ²) arithmetic operations, as compared toO(n ³) operations for the general cases. However, the classical Hankel solvers require the nonsingularity of all leading principal submatrices of the Hankel matrix. The known extensions of these algorithms to general Hankel systems can handle only exactly singular submatrices, but not ill-conditioned ones, and hence they are numerically unstable. In this paper, a stable procedure for solving general nonsingular Hankel systems is presented, using a look-ahead technique to skip over singular or ill-conditioned submatrices. The proposed approach is based on a look-ahead variant of the nonsymmetric Lanczos process that was recently developed by Freund, Gutknecht, and Nachtigal. We first derive a somewhat more general formulation of this look-ahead Lanczos algorithm in terms of formally orthogonal polynomials, which then yields the look-ahead Hankel solver as a special case. We prove some general properties of the resulting look-ahead algorithm for formally orthogonal polynomials. These results are then utilized in the implementation of the Hankel solver. We report some numerical experiments for Hankel systems with ill-conditioned submatrices.The research of the first author was supported by DARPA via Cooperative Agreement NCC 2-387 between NASA and the Universities Space Research Association (USRA).The research of the second author was supported in part by NSF grant DRC-8412314 and Cooperative Agreement NCC 2-387 between NASA and the Universities Space Research Association (USRA).