Matrix Algorithms using Quadtrees

Many scheduling and synchronization problems for large-scale multiprocessing can be overcome using functional (or applicative) programming. With this observation, it is strange that so much attention within the functional programming community has focused on the "aggregate update problem" [10]: essentially how to implement FORTRAN arrays. This situation is strange because in-place updating of aggregates belongs more to uniprocessing than to mathematics. Several years ago functional style drew me to treatment ofd-dimensional arrays as 2^d-ary trees; in particular, matrices become quaternary trees or quadtrees. This convention yields efficient recopying-cum-update of any array; recursive, algebraic decomposition of conventional arithmetic algorithms; and uniform representations and algorithms for both dense and sparse matrices. For instance, any nonsingular subtree is a candidate as the pivot block for Gaussian elimination; the restriction actually helps identification of pivot blocks, because searching a tree is easy. A new block-decomposition formulation for LU decomposition, called (L + U); D 0 decomposition, is particularly well suited to quadtrees. It provides efficient representation of intermediate matrices when pivoting on blocks of various sizes, i.e. during "undulant-block" elimination. A given matrix, A is decomposed into two matrices, plus two permutations. Th