OPTIMAL PARALLEL TRIANGULATION OF A SPARSE-MATRIX

被引：25

作者：

HUANG, JW ^{[1
]}

WING, O ^{[1
]}

机构：

[1] COLUMBIA UNIV,DEPT ELECT ENGN,NEW YORK,NY 10027

来源：

IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS | 1979年 / 26卷 / 09期

关键词：

D O I：

10.1109/TCS.1979.1084692

中图分类号：

TM [电工技术]; TN [电子技术、通信技术];

学科分类号：

0808 ; 0809 ;

摘要：

We consider the problem of triangulating a sparse matrix in a parallel processing system and attempt to answer the following questions: 1) How should the rows and columns of the matrix be reordered in order to minimize the completion time of the parallel triangulation process if an unrestricted number of processors are used? 2) if the number of processors is fixed, what is the minimum completion time and how should the parallel Operations be scheduled? Implementation of the parallel algorithm is discussed and experimental results are given. © 1979 IEEE

引用

页码：726 / 732

页数：7

共 17 条

[1]

Aho A. V., 1974, DESIGN ANAL COMPUTER

[2]

BUSSELL B, 1974, 74 P IFIP C NEW YORK, P286

[3]

CALAHAN DA, 1973, 11TH P ALL C CIRC SY

[4]

CHEN NF, 1974, 1974 P SAG COMP C PA, P1

[5]

CONRAD V, 1977, IEEE T COMPUT, V26, P838, DOI 10.1109/TC.1977.1674932

[6] BOUNDS ON NUMBER OF PROCESSORS AND TIME FOR MULTIPROCESSOR OPTIMAL SCHEDULES [J].

FERNANDEZ, EB ;

BUSSELL, B .

IEEE TRANSACTIONS ON COMPUTERS, 1973, C-22 (08) :745-751

[7]

HELLER D, 1976, SURVEY PARALLEL ALGO

[8] PARALLEL SEQUENCING AND ASSEMBLY LINE PROBLEMS [J].

HU, TC .

OPERATIONS RESEARCH, 1961, 9 (06) :841-848

[9]

Lambiotte J. J. Jr., 1975, ACM Transactions on Mathematical Software, V1, P308, DOI 10.1145/355656.355658

[10]

POTTLE C, 1976, 1976 P IEEE INT S CI, P394

← 1 2 →