tailieunhanh - Digital Signal Processing Handbook P10

Yagle, . “Fast Matrix Computations” Digital Signal Processing Handbook Ed. Vijay K. Madisetti and Douglas B. Williams Boca Raton: CRC Press LLC, 1999 c 1999 by CRC Press LLC .10 Fast Matrix Computations Introduction Divide-and-Conquer Fast Matrix Multiplication Strassen Algorithm • Divide-and-Conquer • Arbitrary Precision Approximation (APA) Algorithms • Number Theoretic Transform (NTT) Based Algorithms Overview • The Wavelet Transform • Wavelet Representations of Integral Operators • Heuristic Interpretation of Wavelet Sparsification Wavelet-Based Matrix Sparsification Andrew E. Yagle University of Michigan References Introduction This chapter presents two major approaches to fast matrix multiplication. We restrict our attention to matrix multiplication, excluding matrix addition and matrix inversion, since matrix addition. | Yagle . Fast Matrix Computations Digital Signal Processing Handbook Ed. Vijay K. Madisetti and Douglas B. Williams Boca Raton CRC Press LLC 1999 1999 by CRC Press LLC 10 Fast Matrix Computations Andrew E. Yagle University of Michigan Introduction Divide-and-Conquer Fast Matrix Multiplication Strassen Algorithm Divide-and-Conquer Arbitrary Precision Approximation APA Algorithms Number Theoretic Transform NTT Based Algorithms Wavelet-Based Matrix Sparsification Overview The Wavelet Transform Wavelet Representations of Integral Operators Heuristic Interpretation of Wavelet Sparsification References Introduction This chapter presents two major approaches to fast matrix multiplication. We restrict our attention to matrix multiplication excluding matrix addition and matrix inversion since matrix addition admits no fast algorithm structure save for the obvious parallelization and matrix inversion . solution of large linear systems of equations is generally performed by iterative algorithms that require repeated matrix-matrix or matrix-vector multiplications. Hence matrix multiplication is the real problem of interest. We present two major approaches to fast matrix multiplication. The first is the divide-and-conquer strategy made possible by Strassen s 1 remarkable reformulation of non-commutative 2 x 2 matrix multiplication. We also present the APA arbitrary precision approximation algorithms which improve on Strassen s result at the price of approximation and a recent result that reformulates matrix multiplication as convolution and applies number theoretic transforms. The second approach is to use a wavelet basis to sparsify the representation of Calderon-Zygmund operators as matrices. Since electromagnetic Green s functions are Calderon-Zygmund operators this has proven to be useful in solving integral equations in electromagnetics. The sparsified matrix representation is used in an iterative algorithm to solve the linear system of equations .