ARC Graphs and Their Possible Application to Sparse Matrix Problems.
Abstract
In continuation of earlier work on the graph language GRAAL for describing and implementing graph algorithms, the report introduces a new type of graph representation involving solely the arcs and their incidence relations and leaving the nodes implicitly defined. In line with the set theoretical foundation of GRAAL, the arc graph structure is defined in terms of four Boolean mapping over the power set of the arcs. A simple data structure is available for arc graphs requiring only storage of the order of the arc set itself. As an application, algorithms for the LU decomposition of a matrix and the solution of sparse linear systems are formulated in terms of arc graphs and their operators. Furthermore, the report describes a subroutine test package for experimentation with the arc graph representation, which is then used to implement and test the sparse matrix algorithms. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 01, 1973
- Accession Number
- AD0759785
Entities
People
- Charles K. Mesztenyi
- Werner Rheinboldt
Organizations
- University of Maryland