### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Special Topics CS 8803

GPA 3.81

### View Full Document

## 35

## 0

## Popular in Course

## Popular in ComputerScienence

This 0 page Class Notes was uploaded by Alayna Veum on Monday November 2, 2015. The Class Notes belongs to CS 8803 at Georgia Institute of Technology - Main Campus taught by Michael Best in Fall. Since its upload, it has received 35 views. For similar materials see /class/234091/cs-8803-georgia-institute-of-technology-main-campus in ComputerScienence at Georgia Institute of Technology - Main Campus.

## Reviews for Special Topics

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 11/02/15

CS 8803 NMC Numerical Methods in Computational Science and Engineering Matrix Computations Haesun Park hparkcc gatech edu Division of Computational Science and Engineering College of Computing Georgia Institute of Technology Atlanta GA 30332 USA Lecture 1 August 21 2007 What is Numerical Analysis Three great branches of science Theory Experiment and Computation The purpose of computing is insight not numbers 1961 Hamming i Numerical Analysis is Study of Algorithms for Problems of Continuous Mathematics Ex Newton s method Lagrange interpolation polynomial Gaussian Elimination Euler s method m Computational mathematics is mainly based on two ideas extreme simplification Taylor series and linear algebra 1 Role of Computers in Numerical Computing Computers certainly play a part in numerical computing but even if rounding error vanishes 95 of numerical analysis would remain Most mathematical problems cannot be solved by a finite sequence of elementary operations Need fast algorithms that converge to approximate answers accurate to many digits of precision in science and engineering applications CS 8803 NMC Numerical Methods in Computational Science and Engineering Matrix Computations 0120 Different Types of Problems in Numerical Computing Problem F can be solved in a finite sequence of elementary operations Root for polynomial of degree 4 closed form formula exists Ferrari 1540 i Solving linear equations Linear programming Problem I cannot be solved in a finite sequence of elementary operations I Root for polynomial of degree 5 and higher no closed form formula exisits Ruffini and Abel around 1800 I Finding eigenvalues of an n x 72 matrix with n 2 5 il Minimize a function of several variables I Evaluate an integral I solve an ODE solve a PDE Problem F is not necessarily easier than Problem When problem dimension is very high one often ignores the exact solution and uses approximate and fast methods instead World s largest matrix computation as of April 2007 Google s PageRank eigenvector of a matrix of order 27 billion CS 8803 NMC Numerical Methods in Computational Science and Engineering Matrix Computations 0220 Gauss 17771855 and Numerical Computing i least squares data fitting 1795 systems of linear equations 1809 numerical quadrature 1814 i fast Fourier transform 1805 not well known until it was rediscovered by Cooley and Tukey 1965 Numerical Linear Algebra i square linear system solving least squares problems i eigenvalue problem Often Algorithms Matrix Factorizations CS 8803 NMC Numerical Methods in Computational Science and Engineering Matrix Computations 0320 Square Linear System Solving When does the solution exist Q When is it easy to solve E Diagonalization expensive E Make it triangular A LU lower upper triangular factors a Gaussian elimination make the problem into triangular system solving May break down A 1 1 Even for matrices with the LU factorization it can be unstable Pivoting By interchanging rows stability can be achieved Gaussian elimination with pivoting PA LU Discovery of pivoting was easy but its theoretical analysis has been hard For most matrices it is stable but in 1960 V lkinson and others found that for certain exceptional matrices Gaussian elimination with pivoting is unstable CS 8803 NMC Numerical Methods in Computational Science and Engineering Matrix Computations 0420 Orthogonal Unitary Transformations E Use of orthogonal matrices was introduced in late 1950 s A Q 6 RMquot with Q 1 QT orQ 6 CWquot with Q 1 QT i QR factorization For any matrix A m x n m gt 72 a QR factorization of A exists A Q i where Q m x m has orthonormal colummns and R n x n is upper triangular Reduced QRD A Q1R where Q 6217622 u Gram1883Schmidt1907 orthogonalization column of Q are obtained and it gets R as a by product in the process of triangular orthogonalization n Modified GramSchmidt Laplace 1816 Rice 1966 i Householder method 1958 Householder reflector Turnbull and Aitken 1932 A is reduced to an upper triangular matrix R via orthogonal operations More stable numerically because orthogonal operations preserve L2 and Frobenius norms and thus do not amplify the rounding errors introduced at each step H I 2vavTv 22 0 a Givens method extension of 2x2 plane rotations c s 0080 sm0 plane rotations s c 3an 0080 CS 8803 NMC Numerical Methods in Computational Science and Engineering Matrix Computations 0520 Important matrix computation algorithms in 1960s Based on the QR factorization to solve the least squares construct orthonormal bases i used at the core of other algorithms especially in EVD and SVD algorithms CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 0620 Least Squares Q Overdetermined system solving Ax z b where A m x n with m 2 72 If a square system we know how to solve normal equations or QRD E Reduced QR Decomposition distance preserving dimension reduction method m QRD efficient updating and downdating methods exist W Rank Deficiency Q is not the basis for rangeR if rankA is not full m Pivoted QR decomposition Rank Revealing QR decomposition or the SVD is needed if rankA is not full CS 8803 NMC Numerical Methods in Computational Science and Engineering Matrix Computations 0720 Singular Value Decomposition SVD Beltrami Jordan Sylvester in the late 19th century made well known by Golub 1965 a The SVD Any matrix A E CmXquot assume m gt 72 but not necessary can be decomposed into A UEVT where U E mem is unitary V 6 CMquot is unitary and E E Rm gt 0 is diagonal Z diagc71 on with 71 Z 72 Z 2 an 2 0 If aquot gt n1 0 then rankA 7quot 1 AP 2 UprV p g rankA is the best rankp approximation of A a singular values of A are the nonnegative square roots of the eigenvalues of ATA ATA VETEVT and AAT UZETUT Latent Semantic Indexing lower rank approximation of the termdocument matrix i Principal Component Analysis Let 0 A ceT Then the leading singular vectors are the PCA solutions Let the SVD of O UEVT Then OCT 2 UEETVT So Uh is the k principal vectors i But SVD is expensive CS 8803 NMC Numerical Methods in Computational Science and Engineering Matrix Computations 0820

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.