PREDICTING STRUCTURE IN SPARSE-MATRIX COMPUTATIONS

被引：68

作者：

GILBERT, JR

机构：

[1] UNIV ICELAND,REYKJAVIK,ICELAND

[2] UNIV MINNESOTA,INST MATH & APPLICAT,MINNEAPOLIS,MN 55455

来源：

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS | 1994年 / 15卷 / 01期

关键词：

SPARSE MATRIX ALGORITHMS; GRAPH THEORY; MATRIX FACTORIZATION; SYSTEMS OF LINEAR EQUATIONS; EIGENVECTORS;

D O I：

10.1137/S0895479887139455

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Many sparse matrix algorithms-for example, solving a sparse system of linear equations-begin by predicting the nonzero structure of the output of a matrix computation from the nonzero structure of its input. This paper is a catalog of ways to predict nonzero structure. It contains known results for some problems, including various matrix factorizations, and new results for other problems, including some eigenvector computations.

引用

页码：62 / 79

页数：18

共 39 条

[1] OPTIMAL PARALLEL SOLUTION OF SPARSE TRIANGULAR SYSTEMS [J].

ALVARADO, FL ;

SCHREIBER, R .

SIAM JOURNAL ON SCIENTIFIC COMPUTING, 1993, 14 (02) :446-460

[2] INHERITED MATRIX ENTRIES - PRINCIPAL SUBMATRICES OF THE INVERSE [J].

BARRETT, WW ;

JOHNSON, CR ;

OLESKY, DD ;

VANDENDRIESSCHE, P .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1987, 8 (03) :313-322

[3] SOME RESULTS ON SPARSE MATRICES [J].

BRAYTON, RK ;

GUSTAVSO.FG ;

WILLOUGH.RA .

MATHEMATICS OF COMPUTATION, 1970, 24 (112) :937-&

[4] THE NULL SPACE PROBLEM .1. COMPLEXITY [J].

COLEMAN, TF ;

POTHEN, A .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1986, 7 (04) :527-537

[5] PREDICTING FILL FOR SPARSE ORTHOGONAL FACTORIZATION [J].

COLEMAN, TF ;

EDENBRANDT, A ;

GILBERT, JR .

JOURNAL OF THE ACM, 1986, 33 (03) :517-532

[6] THE NULL SPACE PROBLEM .2. ALGORITHMS [J].

COLEMAN, TF ;

POTHEN, A .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1987, 8 (04) :544-563

[7]

Duff I. S., 1979, ACM Transactions on Mathematical Software, V5, P18, DOI 10.1145/355815.355817

[8] ON ALGORITHMS FOR OBTAINING A MAXIMUM TRANSVERSAL [J].

DUFF, IS .

ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE, 1981, 7 (03) :315-330

[9]

DUFF IS, 1985, ANL51 MATH COMP SCI

[10]

EDENBRANDT A, 1985, THESIS CORNELL U ITH

← 1 2 3 4 →