UCSB CS 240A - SOLVING AX (25 pages)

Previewing pages 1, 2, 24, 25 of 25 page document View the full content.
View Full Document

SOLVING AX



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

View the full content.
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

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

Loading Unlocking...
Login

Join to view SOLVING AX and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view SOLVING AX and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?