PARALLEL SPARSE-MATRIX SOLUTION AND PERFORMANCE

被引：7

作者：

ALAGHBAND, G

机构：

[1] University of Colorado, Denver Department of Computer Science and Engineering, Denver, CO 80217-3364, Campus Box 109

来源：

PARALLEL COMPUTING | 1995年 / 21卷 / 09期

关键词：

SPARSE LINEAR SYSTEM; LU DECOMPOSITION; SHARED MEMORY MULTIPROCESSOR; PARALLEL PIVOTING STRATEGY; BACK SUBSTITUTION;

D O I：

10.1016/0167-8191(95)00029-N

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

A parallel solution to the large sparse systems of linear equations is presented. The solution method is based on a parallel pivoting technique for LU decomposition on a shared memory MIMD multiprocessor. At each application of the algorithm to the matrix several pivots for reducing the matrix in parallel are generated. During parallel pivoting steps only symmetric permutations are possible. Unsymmetric permutation for numerical stability however is possible during single pivoting steps. We will report on switching between parallel and single pivoting steps to assure numerical stability. Once the matrix is decomposed, the parallel pivoting information is used to solve structurally identical matrices repeatedly. The algorithms, their implementation, and the performance of the solution methods on actual multiprocessors are presented. Based on the resulting triangular matrix structure, two algorithms for back substitution are presented and their performance is compared.

引用

页码：1407 / 1430

页数：24

共 19 条

[1] PARALLEL PIVOTING COMBINED WITH PARALLEL REDUCTION AND FILL-IN CONTROL [J].

ALAGHBAND, G .

PARALLEL COMPUTING, 1989, 11 (02) :201-221

[2] SPARSE GAUSSIAN-ELIMINATION WITH CONTROLLED FILL-IN ON A SHARED MEMORY MULTIPROCESSOR [J].

ALAGHBAND, G ;

JORDAN, HF .

IEEE TRANSACTIONS ON COMPUTERS, 1989, 38 (11) :1539-1557

[3]

ALAGHBAND G, 1983, CSDG833 U COL EL COM

[4]

CALAHAN DA, 1973, 11TH P ANN ALL C CIR, P729

[5]

DAVIS TA, 1993, TR93018 U FLOR COMP

[6]

DUFF IS, 1985, ANL49 MATH COMP SCI

[7] OPTIMAL PARALLEL TRIANGULATION OF A SPARSE-MATRIX [J].

HUANG, JW ;

WING, O .

IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS, 1979, 26 (09) :726-732

[8]

JESS JAG, 1982, IEEE T COMPUT, V31, P231, DOI 10.1109/TC.1982.1675979

[9]

Kohavi Z., 1978, SWITCHING FINITE AUT

[10]

LEUZE MR, 1984, ICASE8447 REP

← 1 2 →