Solving sparse linear least squares problems on some supercomputers by using large dense blocks

Per Christian Hansen, T Ostromsky, A Sameh, Z Zlatev

    Research output: Contribution to journalJournal articleResearchpeer-review


    Efficient subroutines for dense matrix computations have recently been developed and are available on many high-speed computers. On some computers the speed of many dense matrix operations is near to the peak-performance. For sparse matrices storage and operations can be saved by operating only and storing only nonzero elements. However, the price is a great degradation of the speed of computations on supercomputers (due to the use of indirect addresses, to the need to insert new nonzeros in the sparse storage scheme, to the lack of data locality, etc.). On many high-speed computers a dense matrix technique is preferable to sparse matrix technique when the matrices are not large, because the high computational speed compensates fully the disadvantages of using more arithmetic operations and more storage. For very large matrices the computations must be organized as a sequence of tasks in each of which a dense block is treated. The blocks must be large enough to achieve a high computational speed, but not too large, because this will lead to a large increase in both the computing time and the storage. A special "locally optimized reordering algorithm" (LORA) is described, which reorders the matrix so that dense blocks can be constructed and treated with some standard software, say LAPACK or NAG. These ideas are implemented for linear least-squares problems. The rectangular matrices (that appear in such problems) are decomposed by an orthogonal method. Results obtained on a CRAY C92A computer demonstrate the efficiency of using large dense blocks
    Original languageEnglish
    Issue number3
    Pages (from-to)535-558
    Publication statusPublished - 1997


    Dive into the research topics of 'Solving sparse linear least squares problems on some supercomputers by using large dense blocks'. Together they form a unique fingerprint.

    Cite this