Date: Wed, 20 Nov 1996 19:14:38 GMT Server: Apache/1.0.3 Content-type: text/html Content-length: 2791 Last-modified: Fri, 01 Dec 1995 21:56:56 GMT Algorithms for Quadtree Representation of Matrices

Algorithms for Quadtree Representation of Matrices

Description:
Rather than decomposing matrices into rows, columns or tiny blocks, we decompose them recursively into quadrants. The array becomes a tree which still might be stored sequentially, and decompostion of the problem for multiprocessing follows the subtrees. We explore this structure as an exercise of the thesis that functional programming is ideal for multiprocessing; the resulting algorithms are expressed in C for better performance.
Opportunites for ``new'' algorithms abound. Sparse matrices have many empty subtrees, and simple algebra there; so, uniform algorithms can be applied to both sparse and nonsparse problems. Search problems (e.g. pivoting) steer by summary information that ``decorates'' interior nodes of the tree. Under Gaussian elimination, a nonsingular subtree of any order can be eliminated at any step; the resulting ``undulant'' pivoting has been developed for both exact and floating-point decomposition .

Associated Faculty: David S. Wise ( dswise ), Randall Bramley ( bramley ).

Associated Graduate Students: Jeremy Frens ( jfrens ).

Support: Supported in part by the National Science Foundation under a grant numbered CDA93-03189 .

Return to IU Computer Science Research