# UCSB CS 240A - SOLVING AX (25 pages)

Previewing pages*1, 2, 24, 25*of 25 page document

**View the full content.**# SOLVING AX

Previewing pages *1, 2, 24, 25*
of
actual document.

**View the full content.**View Full Document

## SOLVING AX

0 0 114 views

Lecture Notes

- Pages:
- 25
- School:
- University of California, Santa Barbara
- Course:
- Cs 240a - Applied Parallel Computing

**Unformatted text preview: **

CS 240A Solving Ax b in parallel Dense A Gaussian elimination with partial pivoting Same flavor as matrix matrix but more complicated Sparse A Iterative methods Conjugate gradient etc Sparse matrix times dense vector Sparse A Gaussian elimination Cholesky LU etc Graph algorithms Sparse A Preconditioned iterative methods and multigrid Mixture of lots of things CS267 Dense Linear Algebra I 1 Demmel Fa 2001 CS 240A Solving Ax b in parallel Dense A Gaussian elimination with partial pivoting Same flavor as matrix matrix but more complicated Sparse A Iterative methods Conjugate gradient etc Sparse matrix times dense vector Sparse A Gaussian elimination Cholesky LU etc Graph algorithms Sparse A Preconditioned iterative methods and multigrid Mixture of lots of things CS267 Dense Linear Algebra I 2 Demmel Fa 2001 Dense Linear Algebra Excerpts James Demmel http www cs berkeley edu demmel cs267 221001 ppt CS267 Dense Linear Algebra I 3 Demmel Fa 2001 Motivation 3 Basic Linear Algebra Problems Linear Equations Solve Ax b for x Least Squares Find x that minimizes S r 2 where r Ax b i Eigenvalues Find l and x where Ax l x Lots of variations depending on structure of A eg symmetry Why dense A as opposed to sparse A Aren t most large matrices sparse Dense algorithms easier to understand Some applications yields large dense matrices Ax b Computational Electromagnetics CS267 Ax lx Quantum Chemistry Benchmarking How fast is your computer How fast can you solve dense Ax b Dense Linear Algebra I 4 Demmel Fa 2001 Large sparse matrix algorithms often yield smaller but still large Review of Gaussian Elimination GE for solving Ax b Add multiples of each row to later rows to make A upper triangular Solve resulting triangular system Ux c by substitution for each column i zero it out below the diagonal by adding multiples of row i to later rows for i 1 to n 1 for each row j below row i for j i 1 to n add a multiple of row i to row j for k i to n A j k A j k A j i A i i A i k CS267 Dense Linear

View Full Document