Linear Algebra at Large Scale

Transcript

1. Linear Algebra at Large Scale Elizabeth Ramirez @eramirem
2. Computational Engineer We model complex systems on the planet, like forestry and agriculture using satellite imagery.
4. Top 10 Algorithms of the 20th Century
5. Often the most expensive computations in large-scale codes. Curse of Dimensionality
6. Linear Systems Nonlinear Systems Machine Learning Deep Learning
7. Most ubiquitous problem in Scientific Computing and Data Analysis
8. What solves? Systems of Equations Polynomial Interpolation Linear Least-Squares
9. What we know? Gaussian Elimination Complexity
10. HPC Alternative: Iterative Methods General Form
11. Jacobi Gauss-Seidel
12. Convergence of Basic Iterative Methods Spectral radius
13. Krylov Subspaces
14. Conjugate Gradient Method (CG) i) ii)
15. Conjugate Gradient (CG)
16. Bi-conjugate gradient (BiCG) Any linear system
17. Deep Learning Primitives Weights, inputs, outputs stored in tensors Matrix Multiplication Convolution Inner Product Transposition Rectified Linear Unit (ReLu)
18. Matrix Multiplication Fundamental task Naive: Strassen:
19. Low-Rank Approximation Accelerates matrix multiplication, therefore, accelerates convolution. Requires SVD:
20. Low-Rank Multiplication:
21. Single Instruction Multiple Data (SIMD) Data-level parallelism Incompatible with code designed for sequential processors Instruction set available in commercial CPUs and GPGPUs
22. Intel® Math Kernel Library (Intel® MKL) Improved Matrix Multiplication Performance in LAPACK LU decomposition and inverse without pivoting Take advantage of SIMD instruction set In summary: High Performance Linear Algebra
24. References http://www.siam.org/pdf/news/637.pdf https://software.intel.com/en-us/mkl https://software.intel.com/en-us/articles/t ensorflow-optimizations-on-modern-intel-arc hitecture