ACM SIGPLAN Notices · 2003 · 26 citations · 16 references
ComputingComputer EngineeringComputer ScienceAlgorithmsParallel AlgorithmsParallel ComputingData ParallelismMatrix ComputationMemory HierarchyMemory Hierarchy DesignParallel ArchitecturesParallel Numerical Linear AlgebraMemory Hierarchy AlgorithmsParallel Divide And ConquerParallel Matrix AlgorithmsParallel Matrix ComputationParallel Matrix FactorizationParallel Sparse Linear AlgebraRotationsSparse Matrix Computation
Quadtree matrices using Morton-order storage provide natural blocking on every level of a memory hierarchy. Writing the natural recursive algorithms to take advantage of this blocking results in code that honors the memory hierarchy without the need for transforming the code. Furthermore, the divide-and-conquer algorithm breaks problems down into independent computations. These independent computations can be dispatched in parallel for straightforward parallel processing.Proof-of-concept is given by an algorithm for QR factorization based on Givens rotations for quadtree matrices in Morton-order storage. The algorithms deliver positive results, competing with and even beating the LAPACK equivalent.
16
Accuracy and stability of numerical algorithms
Choice Reviews Online · 1996 · 2.1K citations
A Transformation System for Developing Recursive Programs
R. M. Burstall, John Darlington · Journal of the ACM · 1977 · 1.3K citations · Full text
The Computer Science Department.
Hubert Tolman · 1971 · 552 citations
Albert D. Alexandrov, Mihai Ionescu, Klaus E. Schauser et al. · 1995 · 490 citations