A note on properties of splittings of singular symmetric positive semidefinite matrices

Summary. Recently, Benzi and Szyld have published an important paper [1] concerning the existence and uniqueness of splittings for singular matrices. However, the assertion in Theorem 3.9 on the inheriting property of P-regular splitting for singular symmetric positive semidefinite matrices seems to be incorrect. As a complement of paper [1], in this short note we point out that if a matrix T is resulted from a P-regular splitting of a symmetric positive semidefinite matrix A, then splittings induced by T are not all P-regular. Received January 7, 1999 / Published online December 19, 2000     

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.     

Incomplete block-matrix factorization iterative methods for convection-diffusion problems

Standard Galerkin finite element methods or finite difference methods for singular perturbation problems lead to strongly unsymmetric matrices, which furthermore are in general notM-matrices. Accordingly, preconditioned iterative methods such as preconditioned (generalized) conjugate gradient methods, which have turned out to be very successful for symmetric and positive definite problems, can fail to converge or require an excessive number of iterations for singular perturbation problems.This is not so much due to the asymmetry, as it is to the fact that the spectrum can have both eigenvalues with positive and negative real parts, or eigenvalues with arbitrary small positive real parts and nonnegligible imaginary parts. This will be the case for a standard Galerkin method, unless the meshparameterh is chosen excessively small. There exist other discretization methods, however, for which the corresponding bilinear form is coercive, whence its finite element matrix has only eigenvalues with positive real parts; in fact, the real parts are positive uniformly in the singular perturbation parameter.In the present paper we examine the streamline diffusion finite element method in this respect. It is found that incomplete block-matrix factorization methods, both on classical form and on an inverse-free (vectorizable) form, coupled with a general least squares conjugate gradient method, can work exceptionally well on this type of problem. The number of iterations is sometimes significantly smaller than for the corresponding almost symmetric problem where the velocity field is close to zero or the singular perturbation parameter =1.The 2 ^nd author's research was sponsored by Control Data Corporation through its PACER fellowship program.The 3 ^rd author's research was supported by the Netherlands organization for scientific research (NWO).On leave from the Institute of Mathematics, Academy of Science, 1090 Sofia, P.O. Box 373, Bulgaria.     

实对称五对角矩阵Procrustes问题

本文研究了实对称五对角矩阵Procrustes.利用矩阵的奇异值分解简化问题,得到了实对称五对角矩阵X极小化,最后给出数值算例说明方法的有效性.     

The structured total least‐squares approach for non‐linearly structured matrices

In this paper, an extension of the structured total least‐squares (STLS) approach for non‐linearly structured matrices is presented in the so‐called ‘Riemannian singular value decomposition’ (RiSVD) framework. It is shown that this type of STLS problem can be solved by solving a set of Riemannian SVD equations. For small perturbations the problem can be reformulated into finding the smallest singular value and the corresponding right singular vector of this Riemannian SVD. A heuristic algorithm is proposed. Some examples of Vandermonde‐type matrices are used to demonstrate the improved accuracy of the obtained parameter estimator when compared to other methods such as least squares (LS) or total least squares (TLS). Copyright © 2002 John Wiley & Sons, Ltd.     

The symmetric procrustes problem

The following symmetric Procrustes problem arises in the determination of the strain matrix of an elastic structure: find the symmetric matrixX which minimises the Frobenius (or Euclidean) norm ofAX — B, whereA andB are given rectangular matrices. We use the singular value decomposition to analyse the problem and to derive a stable method for its solution. A perturbation result is derived and used to assess the stability of methods based on solving normal equations. Some comparisons with the standard, unconstrained least squares problem are given.     

Generalization of convergence conditions for a restarted GMRES

We consider the GMRES(s), i.e. the restarted GMRES with restart s for the solution of linear systems Ax = b with complex coefficient matrices. It is well known that the GMRES(s) applied on a real system is convergent if the symmetric part of the matrix A is positive definite. This paper introduces sufficient conditions implying the convergence of a restarted GMRES for a more general class of non‐Hermitian matrices. For real systems these conditions generalize the known result initiated as above. The discussion after the main theorem concentrates on the question of how to find an integer j such that the GMRES(s) converges for all s ≥ j. Additional properties of GMRES obtained by derivation of the main theorem are presented in the last section. Copyright © 2000 John Wiley & Sons, Ltd.     

On the solutions of the equation AXB = C under Toeplitz‐like and Hankel matrices constraint

In this paper, we are mainly concerned with 2 types of constrained matrix equation problems of the form AXB=C, the least squares problem and the optimal approximation problem, and we consider several constraint matrices, such as general Toeplitz matrices, upper triangular Toeplitz matrices, lower triangular Toeplitz matrices, symmetric Toeplitz matrices, and Hankel matrices. In the first problem, owing to the special structure of the constraint matrix , we construct special algorithms; necessary and sufficient conditions are obtained about the existence and uniqueness for the solutions. In the second problem, we use von Neumann alternating projection algorithm to obtain the solutions of problem. Then we give 2 numerical examples to demonstrate the effectiveness of the algorithms.     

A note on simultaneous preconditioning and symmetrization of non‐symmetric linear systems

Motivated by the theory of self‐duality that provides a variational formulation and resolution for non‐self‐adjoint partial differential equations (Ann. Inst. Henri Poincaré (C) Anal Non Linéaire 2007; 24 :171–205; Selfdual Partial Differential Systems and Their Variational Principles. Springer: New York, 2008), we propose new templates for solving large non‐symmetric linear systems. The method consists of combining a new scheme that simultaneously preconditions and symmetrizes the problem, with various well‐known iterative methods for solving linear and symmetric problems. The approach seems to be efficient when dealing with certain ill‐conditioned, and highly non‐symmetric systems. The numerical and theoretical results are provided to show the efficiency of our approach. Copyright © 2010 John Wiley & Sons, Ltd.     

Newton's Problem of the Body of Minimal Resistance in the Class of Convex Developable Functions

We investigate the minimization of Newton's functional for the problem of the body of minimal resistance with maximal height M > 0 [4] in the class of convex developable functions defined in a disc. This class is a natural candidate to find a (non–radial) minimizer in accordance with the results of [9]. We prove that the minimizer in this class has a minimal set in the form of a regular polygon with n sides centered in the disc, and numerical experiments indicate that the natural number n > 2 is a non–decreasing function of M. The corresponding functions all achieve a lower value of the functional than the optimal radially symmetric function with the same height M.     

Convergence of a fourth-order singular perturbation of the n-dimensional radially symmetric Monge–Ampère equation

This paper concerns with the convergence analysis of a fourth-order singular perturbation of the Dirichlet Monge–Ampère problem in the n-dimensional radial symmetric case. A detailed study of the fourth- order problem is presented. In particular, various a priori estimates with explicit dependence on the perturbation parameter ε are derived, and a crucial convexity property is also proved for the solution of the fourth-order problem. Using these estimates and the convexity property, we prove that the solution of the perturbed problem converges uniformly and compactly to the unique convex viscosity solution of the Dirichlet Monge–Ampère problem. Rates of convergence in the H^k-norm for k = 0, 1, 2 are also established.     

A family of non class-regular symmetric transversal designs of spread type

Many classes of symmetric transversal designs have been constructed from generalized Hadamard matrices and they are necessarily class regular. In (Hiramine, Des Codes Cryptogr 56:21–33, 2010) we constructed symmetric transversal designs using spreads of \mathbbZ_p²ⁿ{\mathbb{Z}_p^{2n}} with p a prime. In this article we show that most of them admit no class regular automorphism groups. This implies that they are never obtained from generalized Hadamard matrices. As far as we know, this is the first infinite family of non class-regular symmetric transversal designs.     

Symmetric tensor decomposition by alternating gradient descent

The symmetric tensor decomposition problem is a fundamental problem in many fields, which appealing for investigation. In general, greedy algorithm is used for tensor decomposition. That is, we first find the largest singular value and singular vector and subtract the corresponding component from tensor, then repeat the process. In this article, we focus on designing one effective algorithm and giving its convergence analysis. We introduce an exceedingly simple and fast algorithm for rank-one approximation of symmetric tensor decomposition. Throughout variable splitting, we solve symmetric tensor decomposition problem by minimizing a multiconvex optimization problem. We use alternating gradient descent algorithm to solve. Although we focus on symmetric tensors in this article, the method can be extended to nonsymmetric tensors in some cases. Additionally, we also give some theoretical analysis about our alternating gradient descent algorithm. We prove that alternating gradient descent algorithm converges linearly to global minimizer. We also provide numerical results to show the effectiveness of the algorithm.     

Solution of symmetric linear complementarity problems by iterative methods

A unified treatment is given for iterative algorithms for the solution of the symmetric linear complementarity problem: $$Mx + q \geqslant 0, x \geqslant 0, x^T (Mx + q) = 0$$ , whereM is a givenn×n symmetric real matrix andq is a givenn×1 vector. A general algorithm is proposed in which relaxation may be performed both before and after projection on the nonnegative orthant. The algorithm includes, as special cases, extensions of the Jacobi, Gauss-Seidel, and nonsymmetric and symmetric successive over-relaxation methods for solving the symmetric linear complementarity problem. It is shown first that any accumulation point of the iterates generated by the general algorithm solves the linear complementarity problem. It is then shown that a class of matrices, for which the existence of an accumulation point that solves the linear complementarity problem is guaranteed, includes symmetric copositive plus matrices which satisfy a qualification of the type: $$Mx + q > 0 for some x in R^n $$ . Also included are symmetric positive-semidefinite matrices satisfying this qualification, symmetric, strictly copositive matrices, and symmetric positive matrices. Furthermore, whenM is symmetric, copositive plus, and has nonzero principal subdeterminants, it is shown that the entire sequence of iterates converges to a solution of the linear complementarity problem.     

More on extremal ranks of the matrix expressions A − BX ± X*B* with statistical applications

Through a Hermitian‐type (skew‐Hermitian‐type) singular value decomposition for pair of matrices (A, B) introduced by Zha (Linear Algebra Appl. 1996; 240 :199–205), where A is Hermitian (skew‐Hermitian), we show how to find a Hermitian (skew‐Hermitian) matrix X such that the matrix expressions A ? BX ± X^*B^* achieve their maximal and minimal possible ranks, respectively. For the consistent matrix equations BX ± X^*B^* = A, we give general solutions through the two kinds of generalized singular value decompositions. As applications to the general linear model {y, Xβ, σ²V}, we discuss the existence of a symmetric matrix G such that Gy is the weighted least‐squares estimator and the best linear unbiased estimator of Xβ, respectively. Copyright © 2007 John Wiley & Sons, Ltd.     

Semiconvergence of block SOR method for singular linear systems with p-cyclic matrices

In this paper, we discuss semiconvergence of the block SOR method for solving singular linear systems with p-cyclic matrices. Some sufficient conditions for the semiconvergence of the block SOR method for solving a general p-cyclic singular system are proved.     

H‐self‐adjoint matrices. Application to radiosity

In computer graphics, in the radiosity context, a linear system Φx=b must be solved and there exists a diagonal positive matrix H such that H Φ is symmetric. In this article, we extend this property to complex matrices: we are interested in matrices which lead to Hermitian matrices under premultiplication by a Hermitian positive‐definite matrix H. We shall prove that these matrices are self‐adjoint with respect to a particular innerproduct defined on ?ⁿ. As a result, like Hermitian matrices, they have real eigenvalues and they are diagonalizable. We shall also show how to extend the Courant–Fisher theorem to this class of matrices. Finally, we shall give a new preconditioning matrix which really improves the convergence speed of the conjugate gradient method used for solving the radiosity problem. Copyright © 2002 John Wiley & Sons, Ltd.     

Approximate inverse computation using Frobenius inner product

Parallel preconditioners are presented for the solution of general linear systems of equations. The computation of these preconditioners is achieved by orthogonal projections related to the Frobenius inner product. So, min_M∈??∥AM?I∥ _F and matrix M₀∈?? corresponding to this minimum (?? being any vectorial subspace of ??_n(?)) are explicitly computed using accumulative formulae in order to reduce computational cost when subspace ?? is extended to another one containing it. Every step, the computation is carried out taking advantage of the previous one, what considerably reduces the amount of work. These general results are illustrated with the subspace of matrices M such that AM is symmetric. The main application is developed for the subspace of matrices with a given sparsity pattern which may be constructed iteratively by augmenting the set of non‐zero entries in each column. Finally, the effectiveness of the sparse preconditioners is illustrated with some numerical experiments. Copyright © 2002 John Wiley & Sons, Ltd.