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

Publication: Research - peer-review › Journal article – Annual report year: 1997

### Standard

**Solving sparse linear least squares problems on some supercomputers by using large dense blocks.** / Hansen, Per Christian; Ostromsky, T; Sameh, A; Zlatev, Z.

Publication: Research - peer-review › Journal article – Annual report year: 1997

### Harvard

*BIT*, vol 37, no. 3, pp. 535-558.

### APA

*BIT*,

*37*(3), 535-558.

### CBE

### MLA

*BIT*. 1997, 37(3). 535-558.

### Vancouver

### Author

### Bibtex

}

### RIS

TY - JOUR

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

A1 - Hansen,Per Christian

A1 - Ostromsky,T

A1 - Sameh,A

A1 - Zlatev,Z

AU - Hansen,Per Christian

AU - Ostromsky,T

AU - Sameh,A

AU - Zlatev,Z

PB - Springer Netherlands

PY - 1997

Y1 - 1997

N2 - 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

AB - 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

JO - BIT

JF - BIT

SN - 0006-3835

IS - 3

VL - 37

SP - 535

EP - 558

ER -