Loading...
Please wait, while we are loading the content...
Similar Documents
Sparse Matrix Computations on an FFP Machine* (Preliminary Version)
| Content Provider | Semantic Scholar |
|---|---|
| Author | Smith, Bernie Todd Singh, Raj Kishor Mag, Gyula A. |
| Copyright Year | 1988 |
| Abstract | We describe and analyze an algorithm for performing Gaussian elim ination on sparse linear systems with an FFP Machine, a small-grain parallel computer. Given an equation Ai = b, where A is an n x n matrix, our algorithm yields a permuted upper-triangular system, from which we obtain z by back-substitution. If A has e non-zero entries and iff fill-ins are created during elimination, then our algorithm solves the system in O(h x (e + f)) time, using O(e + f) processing elements. (The parameter h is the height of the FFP Machine’s connection network, which is O(log(e + f)).) The algorithm makes no assumptions about the structure of A and requires no pre-processing. The pivot order may be given in advance, or it may be chosen at run-time by the Markowitz heuristic with only a linear increase in cost. We also present results of simulations on sample problems, both randomly generated and from the Boeing-Harwell set. The results of the simulations, in operation counts, are used to estimate the performance of an FFP Machine hardware prototype. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://www.computer.org/csdl/proceedings/fmpc/1988/5892/00/00047478.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
