Search

It is easy to verify that if A is a doubly stochastic matrix, then both its normal equations AAT and ATA are also doubly stochastic, but the reciprocal is not true. In this paper, we introduce and analyze the complete class of nonnegative matrices whose normal equations are doubly stochastic. This class contains and extends the class of doubly stochastic matrices to the rectangular case. In particular, we characterize these matrices in terms of their row and column sums and provide results regarding their nonzero structure. We then consider the diagonal equivalence of any rectangular nonnegative matrix to a matrix of this new class, and we identify the properties for such a diagonal equivalence to exist. To this end, we present a scaling algorithm and establish the conditions for its convergence. We also provide numerical experiments to highlight the behavior of the algorithm in the general case. [ABSTRACT FROM AUTHOR]

For the solution of large sparse unsymmetric systems, Duff et al. [SIAM J. Sci. Comput., 37 (2015), pp. A1248-A1269] proposed an approach based on the block Cimmino iterations [Numer. Math., 35 (1980), pp. 1-12], in which the solution is computed in a single iteration, so we call it a pseudodirect solver. In this approach, matrices are augmented with additional variables and constraints so that a partitioning of the matrix in blocks of rows defines mutually orthogonal subspaces. The augmented system can then be solved efficiently with a sum of projections onto these orthogonal subspaces. The purpose of this manuscript is to extend this method to the minimum norm solution of underdetermined systems and to the solution of least-squares problems. In the latter case, a partitioning of the matrix in blocks of columns rather than rows is used, and the system must be suitably augmented to define mutually orthogonal subspaces again to recover the least-squares solution of the original problem. This article proves the equivalence between the solution of the original and the augmented system. In order to complete the extension to overdetermined systems, we also propose an iterative block conjugate gradient acceleration [SIAM J. Sci. Comput., 16 (1995), pp. 1478-1511] for the solution of least-squares problems. The efficiency of both the iterative and the augmented pseudodirect approaches, as implemented in the ABCD-Solver, is illustrated on large rectangular matrices from the SuiteSparse Matrix Collection. [ABSTRACT FROM AUTHOR]

We introduce and study a novel way of accelerating the convergence of the block Cimmino method by augmenting the matrix so that the subspaces corresponding to the partitions are orthogonal. This results in a requirement to solve a relatively smaller symmetric positive definite system. We discuss several issues involved in a parallel implementation and illustrate the performance of our method on some realistic test problems. [ABSTRACT FROM AUTHOR]

As long as a square non-negative matrix A has total support then it can be balanced, that is, we can find a diagonal scaling of A that has row and column sums equal to one. A number of algorithms have been proposed to achieve the balancing, the most well known of these being Sinkhorn–Knopp. In this paper, we derive new algorithms based on inner–outer iteration schemes. We show that Sinkhorn–Knopp belongs to this family, but other members can converge much more quickly. In particular, we show that while stationary iterative methods offer little or no improvement in many cases, a scheme using a preconditioned conjugate gradient method as the inner iteration converges at much lower cost (in terms of matrix–vector products) for a broad range of matrices; and succeeds in cases where the Sinkhorn–Knopp algorithm fails. [ABSTRACT FROM AUTHOR]

When solving the symmetric positive definite (SPD) linear system Ax* = b with the conjugate gradient method, the smallest eigenvalues in the matrix A often slow down the convergence. Consequently if the smallest eigenvalues in A could somehow be ''removed,'' the convergence may be improved. This observation is of importance even when a preconditioner is used, and some extra techniques might be investigated to further improve the convergence rate of the conjugate gradient on the given preconditioned system. Several techniques have been proposed in the literature that consist of either updating the preconditioner or enforcing conjugate gradient to work in the orthogonal complement of an invariant subspace associated with the smallest eigenvalues. The goal of this work is to compare several of these techniques in terms of numerical efficiency. Among various possibilities, we exploit the PARTIAL SPECTRAL FACTORIZATION algorithm presented in [M. Arioli and D. Ruiz, Technical Report RAL-TR-2002-021, Rutherford Appleton Laboratory, Atlas Center, Didcot, Oxfordshire, England, 2002] to compute an orthonormal basis of a near-invariant subspace of A associated with the smallest eigenvalues. This eigeninformation is used in combination with different solution techniques. In particular we consider the deflated version of conjugate gradient. As representative of techniques exploiting the spectral information to update the preconditioner we consider also the approaches that attempt to shift the smallest eigenvalues close to one where most of the eigenvalues of the preconditioned matrix should be located. Finally, we consider an algebraic two-grid scheme inspired by ideas from the multigrid philosophy. In this paper, we describe these various variants and we compare their numerical behavior on a set of model problems from Matrix Market or arising from the discretization via the finite element technique of some two-dimensional (2D) heterogeneous diffusion PDE problems. We discuss their numerical efficiency, computational complexity, and sensitivity to the accuracy of the eigencalculation. [ABSTRACT FROM AUTHOR]