Solving sparse linear least-squares problems on some supercomputers by using large dense blocks |
| |
Authors: | P C Hansen Tz Ostromsky A Sameh Z Zlatev |
| |
Institution: | (1) Institute for Mathematical Modelling, Technical University of Denmark, Bldg. 305, DK-2800 Lyngby, Denmark;(2) Central Laboratory for Parallel Processing, Bulgarian Academy of Sciences, Acad. G. Bonchev Str. Bl. 8, 1113 Sofia, Bulgaria;(3) Computer Science Department, University of Purdue, 47907-1398 Purdue, Indiana, USA;(4) National Environmental Research Institute, Frederiksborgvej 399, P. O. Box 358, DK-4000 Roskilde, Denmark |
| |
Abstract: | 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. |
| |
Keywords: | 65F20 65F25 |
本文献已被 SpringerLink 等数据库收录! |
|