[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
article

Locality of Reference in LU Decomposition with Partial Pivoting

Published: 01 October 1997 Publication History

Abstract

This paper presents a new partitioned algorithm for LU decomposition with partial pivoting. The new algorithm, called the recursively partitioned algorithm, is based on a recursive partitioning of the matrix. The paper analyzes the locality of reference in the new algorithm and the locality of reference in a known and widely used partitioned algorithm for LU decomposition called the right-looking algorithm. The analysis reveals that the new algorithm performs a factor of $\Theta(\sqrt{M/n})$ fewer I/O operations (or cache misses) than the right-looking algorithm, where $n$ is the order of the matrix and $M$ is the size of primary memory. The analysis also determines the optimal block size for the right-looking algorithm. Experimental comparisons between the new algorithm and the right-looking algorithm show that an implementation of the new algorithm outperforms a similarly coded right-looking algorithm on six different RISC architectures, that the new algorithm performs fewer cache misses than any other algorithm tested, and that it benefits more from Strassen's matrix-multiplication algorithm.

Cited By

View all
  • (2024)Evaluation of POSIT Arithmetic with AcceleratorsProceedings of the International Conference on High Performance Computing in Asia-Pacific Region10.1145/3635035.3635046(62-72)Online publication date: 18-Jan-2024
  • (2022)I/O-Optimal Algorithms for Symmetric Linear Algebra KernelsProceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3490148.3538587(423-433)Online publication date: 11-Jul-2022
  • (2021)Recursion Brings Speedup to Out-of-Core TensorCore-based Linear Algebra Algorithms: A Case Study of Classic Gram-Schmidt QR FactorizationProceedings of the 50th International Conference on Parallel Processing10.1145/3472456.3473522(1-11)Online publication date: 9-Aug-2021
  • Show More Cited By

Index Terms

  1. Locality of Reference in LU Decomposition with Partial Pivoting

      Recommendations

      Comments

      Please enable JavaScript to view thecomments powered by Disqus.

      Information & Contributors

      Information

      Published In

      cover image SIAM Journal on Matrix Analysis and Applications
      SIAM Journal on Matrix Analysis and Applications  Volume 18, Issue 4
      Oct. 1997
      303 pages
      ISSN:0895-4798
      • Editor:
      • P. Van Dooren
      Issue’s Table of Contents

      Publisher

      Society for Industrial and Applied Mathematics

      United States

      Publication History

      Published: 01 October 1997

      Author Tags

      1. Gaussian elimination
      2. LU factorization
      3. cache misses
      4. locality of reference
      5. partial pivoting

      Qualifiers

      • Article

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)0
      • Downloads (Last 6 weeks)0
      Reflects downloads up to 04 Jan 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (2024)Evaluation of POSIT Arithmetic with AcceleratorsProceedings of the International Conference on High Performance Computing in Asia-Pacific Region10.1145/3635035.3635046(62-72)Online publication date: 18-Jan-2024
      • (2022)I/O-Optimal Algorithms for Symmetric Linear Algebra KernelsProceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3490148.3538587(423-433)Online publication date: 11-Jul-2022
      • (2021)Recursion Brings Speedup to Out-of-Core TensorCore-based Linear Algebra Algorithms: A Case Study of Classic Gram-Schmidt QR FactorizationProceedings of the 50th International Conference on Parallel Processing10.1145/3472456.3473522(1-11)Online publication date: 9-Aug-2021
      • (2020)On the role of sparsity and DAG constraints for learning linear DAGsProceedings of the 34th International Conference on Neural Information Processing Systems10.5555/3495724.3497230(17943-17954)Online publication date: 6-Dec-2020
      • (2017)Algorithm 979ACM Transactions on Mathematical Software10.1145/306166444:2(1-19)Online publication date: 18-Sep-2017
      • (2016)Recursion based parallelization of exact dense linear algebra routines for Gaussian eliminationParallel Computing10.1016/j.parco.2015.10.00357:C(235-249)Online publication date: 1-Sep-2016
      • (2015)A new face recognition method based on image decomposition for single sample per person problemNeurocomputing10.5555/2779626.2779783160:C(287-299)Online publication date: 21-Jul-2015
      • (2013)Scaling LAPACK panel operations using parallel cache assignmentACM Transactions on Mathematical Software10.1145/2491491.249149239:4(1-30)Online publication date: 23-Jul-2013
      • (2013)Communication efficient gaussian elimination with partial pivoting using a shape morphing data layoutProceedings of the twenty-fifth annual ACM symposium on Parallelism in algorithms and architectures10.1145/2486159.2486198(232-240)Online publication date: 23-Jul-2013
      • (2013)Graph expansion and communication costs of fast matrix multiplicationJournal of the ACM10.1145/2395116.239512159:6(1-23)Online publication date: 9-Jan-2013
      • Show More Cited By

      View Options

      View options

      Media

      Figures

      Other

      Tables

      Share

      Share

      Share this Publication link

      Share on social media