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

Previewing pages 1, 2, 24, 25 of 25 page document
View Full Document

# SOLVING AX

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

View Full Document
View Full Document

## SOLVING AX

114 views

Lecture Notes

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

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

## Access the best Study Guides, Lecture Notes and Practice Exams Unlocking...