Solution of linear least squares via the ABS algorithm

The ABS class for linear and nonlinear systems has been recently introduced by Abaffy, Broyden, Galantai and Spedicato. Here we consider various ways of applying these algorithms to the determination of the minimal euclidean norm solution of over-determined linear systems in the least squares sense. Extensive numerical experiments show that the proposed algorithms are efficient and that one of them usually gives better accuracy than standard implementations of the QR orthogonalization algorithm with Householder reflections.     

COMPUTING KARMARKAR＇S PROJECTIONS QUICKLY BY USING MATRIX FACTORIZATION

in this paper we compute Karmarkar‘s projections quickly using MoorePenrose g-inverse and matrix factorization. So the computation work of (A^T D^2 A)^-1 is decreased.     

An alternating projected gradient algorithm for nonnegative matrix factorization

Due to the extensive applications of nonnegative matrix factorizations (NMFs) of nonnegative matrices, such as in image processing, text mining, spectral data analysis, speech processing, etc., algorithms for NMF have been studied for years. In this paper, we propose a new algorithm for NMF, which is based on an alternating projected gradient (APG) approach. In particular, no zero entries appear in denominators in our algorithm which implies no breakdown occurs, and even if some zero entries appear in numerators new updates can always be improved in our algorithm. It is shown that the effect of our algorithm is better than that of Lee and Seung’s algorithm when we do numerical experiments on two known facial databases and one iris database.     

Efficient algorithms for computing rank-revealing factorizations on a GPU

Standard rank-revealing factorizations such as the singular value decomposition (SVD) and column pivoted QR factorization are challenging to implement efficiently on a GPU. A major difficulty in this regard is the inability of standard algorithms to cast most operations in terms of the Level-3 BLAS. This article presents two alternative algorithms for computing a rank-revealing factorization of the form $\mathsf{A}=\mathsf{U}\mathsf{T}{\mathsf{V}}^{\ast }$, where $\mathsf{U}$ and $\mathsf{V}$ are orthogonal and $\mathsf{T}$ is trapezoidal (or triangular if $\mathsf{A}$ is square). Both algorithms use randomized projection techniques to cast most of the flops in terms of matrix-matrix multiplication, which is exceptionally efficient on the GPU. Numerical experiments illustrate that these algorithms achieve significant acceleration over finely tuned GPU implementations of the SVD while providing low rank approximation errors close to that of the SVD.     

A compound matrix algorithm for the computation of the Smith form of a polynomial matrix

In the present paper is presented a numerical method for the exact reduction of a singlevariable polynomial matrix to its Smith form without finding roots and without applying unimodular transformations. Using the notion of compound matrices, the Smith canonical form of a polynomial matrixM(s)^nxn[s] is calculated directly from its definition, requiring only the construction of all thep-compound matricesC _p (M(s)) ofM(s), 1<pn. This technique produces a stable and accurate numerical algorithm working satisfactorily for any polynomial matrix of any degree.     

A practical algorithm for faster matrix multiplication

The purpose of this paper is to present an algorithm for matrix multiplication based on a formula discovered by Pan [7]. For matrices of order up to 10 000, the nearly optimum tuning of the algorithm results in a rather clear non‐recursive one‐ or two‐level structure with the operation count comparable to that of the Strassen algorithm [9]. The algorithm takes less workspace and has better numerical stability as compared to the Strassen algorithm, especially in Winograd's modification [2]. Moreover, its clearer and more flexible structure is potentially more suitable for efficient implementation on modern supercomputers. Copyright © 1999 John Wiley & Sons, Ltd.     

A lower bound guaranteeing exact matrix completion via singular value thresholding algorithm

In this paper, we give a lower bound guaranteeing exact matrix completion via singular value thresholding (SVT) algorithm. The analysis shows that when the parameter in SVT algorithm is beyond some finite scalar, one can recover some unknown low-rank matrices exactly with high probability by solving a strictly convex optimization problem. Furthermore, we give an explicit expression for such a finite scalar. This result in the paper not only has theoretical interests, but also guides us to choose suitable parameters in the SVT algorithm.     

Computing the nearest diagonally dominant matrix

We solve the problem of minimizing the distance from a given matrix to the set of symmetric and diagonally dominant matrices. First, we characterize the projection onto the cone of diagonally dominant matrices with positive diagonal, and then we apply Dykstra's alternating projection algorithm on this cone and on the subspace of symmetric matrices to obtain the solution. We discuss implementation details and present encouraging preliminary numerical results. Copyright © 1999 John Wiley & Sons, Ltd.     

四元数矩阵方程的复转化及保结构算法

给出四元数矩阵复表示运算定义及其相关性质,并运用复表示运算的保结构特性,讨论了四元数矩阵Moore-Penrose逆计算以及两类四元数矩阵方程AXB=C和AX-XB=C的数值求解方法.数值算例检验了所给算法的可行性.     

Developing the CGLS algorithm for the least squares solutions of the general coupled matrix equations

In the present paper, we consider the minimum norm solutions of the general least squares problem By developing the conjugate gradient least square (CGLS) method, we construct an efficient iterative method to solve this problem. The constructed iterative method can compute the solution group of the problem within a finite number of iterations in the absence of roundoff errors. Also it is shown that the method is stable and robust. Finally, by some numerical experiments, we demonstrate that the iterative method is effective and efficient. Copyright © 2013 John Wiley & Sons, Ltd.     

Least squares solution with the minimum-norm to general matrix equations via iteration

Two iterative algorithms are presented in this paper to solve the minimal norm least squares solution to a general linear matrix equations including the well-known Sylvester matrix equation and Lyapunov matrix equation as special cases. The first algorithm is based on the gradient based searching principle and the other one can be viewed as its dual form. Necessary and sufficient conditions for the step sizes in these two algorithms are proposed to guarantee the convergence of the algorithms for arbitrary initial conditions. Sufficient condition that is easy to compute is also given. Moreover, two methods are proposed to choose the optimal step sizes such that the convergence speeds of the algorithms are maximized. Between these two methods, the first one is to minimize the spectral radius of the iteration matrix and explicit expression for the optimal step size is obtained. The second method is to minimize the square sum of the F-norm of the error matrices produced by the algorithm and it is shown that the optimal step size exits uniquely and lies in an interval. Several numerical examples are given to illustrate the efficiency of the proposed approach.     

Fast rectangular matrix multiplication and some applications

We study asymptotically fast multiplication algorithms for matrix pairs of arbitrary di- mensions, and optimize the exponents of their arithmetic complexity bounds. For a large class of input matrix pairs, we improve the known exponents. We also show some applications of our results:(i) we decrease from O(n~2 n~(1 o)(1)logq)to O(n~(1.9998) n~(1 o(1))logq)the known arithmetic complexity bound for the univariate polynomial factorization of degree n over a finite field with q elements; (ii) we decrease from 2.837 to 2.7945 the known exponent of the work and arithmetic processor bounds for fast deterministic(NC)parallel evaluation of the determinant, the characteristic polynomial, and the inverse of an n×n matrix, as well as for the solution to a nonsingular linear system of n equations; (iii)we decrease from O(m~(1.575)n)to O(m~(1.5356)n)the known bound for computing basic solutions to a linear programming problem with m constraints and n variables.     

A finite algorithm for the Drazin inverse of a polynomial matrix

Based on Greville's finite algorithm for Drazin inverse of a constant matrix we propose a finite numerical algorithm for the Drazin inverse of polynomial matrices. We also present a new proof for Decell's finite algorithm through Greville's finite algorithm.     

Conley's spectral sequence via the sweeping algorithm

In this article we consider a spectral sequence (Er,dr) associated to a filtered Morse-Conley chain complex (C,Δ), where Δ is a connection matrix. The underlying motivation is to understand connection matrices under continuation. We show how the spectral sequence is completely determined by a family of connection matrices. This family is obtained by a sweeping algorithm for Δ over fields F as well as over Z. This algorithm constructs a sequence of similar matrices Δ⁰=Δ,Δ¹,… , where each matrix is related to the others via a change-of-basis matrix. Each matrix Δr over F (resp., over Z) determines the vector space (resp., Z-module) Er and the differential dr. We also prove the integrality of the final matrix ΔR produced by the sweeping algorithm over Z which is quite surprising, mainly because the intermediate matrices in the process may not have this property. Several other properties of the change-of-basis matrices as well as the intermediate matrices Δr are obtained.     

The black-box Niederreiter algorithm and its implementation over the binary field

The most time-consuming part of the Niederreiter algorithm for factoring univariate polynomials over finite fields is the computation of elements of the nullspace of a certain matrix. This paper describes the so-called ``black-box' Niederreiter algorithm, in which these elements are found by using a method developed by Wiedemann. The main advantages over an approach based on Gaussian elimination are that the matrix does not have to be stored in memory and that the computational complexity of this approach is lower. The black-box Niederreiter algorithm for factoring polynomials over the binary field was implemented in the C programming language, and benchmarks for factoring high-degree polynomials over this field are presented. These benchmarks include timings for both a sequential implementation and a parallel implementation running on a small cluster of workstations. In addition, the Wan algorithm, which was recently introduced, is described, and connections between (implementation aspects of) Wan's and Niederreiter's algorithm are given.

     

COMPUTING KARMARKAR＇S PROJECTIONS IN STOCHASTIC LINEAR PROGRAMMING

The Karmarkar‘s projections are computed quickly by using Moore-Penrose g inverse and matrix factorization in stochastic linear programming. So computation work of (AD^2A^T)^-1 is decreased.     

Factorization of the transition matrix for the general Jacobi system

The Jacobi system on a full‐line lattice is considered when it contains additional weight factors. A factorization formula is derived expressing the scattering from such a generalized Jacobi system in terms of the scattering from its fragments. This is performed by writing the transition matrix for the generalized Jacobi system as an ordered matrix product of the transition matrices corresponding to its fragments. The resulting factorization formula resembles the factorization formula for the Schrödinger equation on the full line. Copyright © 2016 John Wiley & Sons, Ltd.