Call Now: (800) 537-1660
 Home    Why?     Free Solver   Testimonials    FAQs    Product    Contact

May 18th

May 18th

# Computational Science and Engineering: Matrix Computations

## What is Numerical Analysis ?

•Three great branches of science:
Theory, Experiment, and Computation
•The purpose of computing is insight, not numbers (1961 Hamming).
•Numerical Analysis is
Study of Algorithms for Problems of Continuous Mathematics.
Ex. Newton’s method, Lagrange interpolation polynomial, Gaussian
Elimination, Euler’s method...
•Computational mathematics is mainly based on two ideas
(extreme simplification) Taylor series and Linear Algebra .
•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.

## 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)
•Solving linear equations
•Linear programming

•Problem I: cannot be solved in a finite sequence of elementary operations:
•Root for polynomial of degree 5 and higher: no closed form formula exisits (Ruffini and Abel, around 1800)
•Finding eigenvalues of an matrix with Minimize a function of several variables
•Evaluate an integral
•solve an ODE
•solve a PDE

Problem F is not necessarily easier than Problem I
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 2.7 billion

## Gauss (1777-1855) and Numerical Computing

least squares data fitting (1795)
systems of linear equations (1809)
•fast Fourier transform (1805) - not well known until it was rediscovered by Cooley and Tukey (1965)

Numerical Linear Algebra
•square linear system solving
•least squares problems
•eigenvalue problem

Often, Algorithms = Matrix Factorizations

## Square Linear System Solving

•When does the solution exist?
•When is it easy to solve?
•Diagonalization: expensive
•Make it triangular: A = LU: lower - upper triangular factors
•Gaussian elimination: make the problem into triangular system solving

May break down:

Even for matrices with the LU factorization, it can be unstable.

•Pivoting: By inter changing rows , stability can be achieved.
Gaussian elimination with pivoting :
Discovery of pivoting was easy but its theoretical analysis has been hard.
For most matrices, it is stable but in 1960 Wilkinson and others found that
for certain exceptional matrices, Gaussian elimination with pivoting is
unstable.

## Orthogonal (Unitary) Transformations

•Use of orthogonal matrices was introduced in late 1950’s

•QR factorization: For any matrix a QR factorization of
A exists

has orthonormal colummns and is upper triangular. Reduced QRD: where
•Gram(1883)-Schmidt(1907) orthogonalization: column of Q are obtained
and it gets R as a by product in the process of triangular orthogonalization
•Modified Gram-Schmidt (Laplace 1816, Rice 1966)

•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 and Frobenius norms and thus do not amplify the rounding
errors introduced at each step :

•Givens method: extension of 2x2 plane rotations

plane rotations:

## Important matrix computation algorithms in 1960s

Based on the QR factorization:

•to solve the least squares
•construct orthonormal bases
•used at the core of other algorithms especially in EVD and SVD algorithms

## Least Squares

•Overde termined system solving
•If a square system, we know how to solve: normal equations, or QRD
•Reduced QR Decomposition: distance preserving dimension reduction method
•QRD: efficient updating and downdating methods exist
•Rank Deficiency: Q is not the basis for range(R) if rank(A) is not full
•Pivoted QR decomposition, Rank Revealing QR decomposition or the SVD is needed if rank(A) is not full

## Singular Value Decomposition (SVD)

•Beltrami, Jordan, Sylvester, in the late 19th century
made well known by Golub 1965

•The SVD: Any matrix (assume but not necessary) can
be decomposed into whereis unitary, is
unitary, andis diagonal,

is the best rank p approximation of A

•singular values of A are the nonnegative square roots of the eigenvalues of

•Latent Semantic Indexing:
lower rank approximation of the term-document matrix

•Principal Component Analysis:
Let
Then the leading singular vectors are the PCA solutions. Let the SVD of
is the k principal vectors

•But SVD is expensive.

## Eigenvalue problem

•Symmetric vs. Non-symmetric
•For which matrices eigenvalues are easy to find?
•What transformations allowed? Similarity transformations. Two matrices A
and B are similar if for a nonsingular matrix X. Then the
characteristic polynomials of A and B are the same.

Algorithms for Symmetric Eigenvalue Problems

•Jacobi algorithm
•QR algorithm (1960)
•One of the matrix factorization algorithms with the greatest impact
•Francis, Kublanovskaya, Wilkinson
•Iterative, in symmetric case, typically it converges cubically
•EISPACK, LAPACK, NAG, IMSL, Numerical recipes, MATLAB, Maple, Mathematica
Power method : to find the leading eigenvalue, eigenvector, PageRank

 Prev Next

Home    Why Algebra Buster?    Guarantee    Testimonials    Ordering    FAQ    About Us
What's new?    Resources    Animated demo    Algebra lessons    Bibliography of     textbooks