Undulant-block elimination and integer-preserving matrix inversion (Q1818305)

A new formulation for LU decomposition is proposed, which allows efficient representation of intermediate matrices while eliminating blocks of various sizes. The efficiency is due to a design intended for block encapsulization, implicit in data structures that are convenient both for process scheduling and for memory management. The corresponding algorithms, expressed naturally as functional programs, are well suited for parallel and distributed processing. An example of a motivating data structure, the quadtree representation for matrices, is reviewed and some algorithms coded in Haskell are provided. Finally, an integer-preserving version is presented replacing Bareiss's algorithm with a parallel equivalent.