## We Promise to Make your Math Frustrations Go Away!

Try the Free Math Solver or Scroll down to Tutorials!

 Depdendent Variable

 Number of equations to solve: 23456789
 Equ. #1:
 Equ. #2:

 Equ. #3:

 Equ. #4:

 Equ. #5:

 Equ. #6:

 Equ. #7:

 Equ. #8:

 Equ. #9:

 Solve for:

 Dependent Variable

 Number of inequalities to solve: 23456789
 Ineq. #1:
 Ineq. #2:

 Ineq. #3:

 Ineq. #4:

 Ineq. #5:

 Ineq. #6:

 Ineq. #7:

 Ineq. #8:

 Ineq. #9:

 Solve for:

 Please use this form if you would like to have this math solver on your website, free of charge. Name: Email: Your Website: Msg:

# Numerical Linear Algebra Background

• matrix structure and algorithm complexity

• solving linear equations with factored matrices

• LU, Cholesky, LDLT factorization

• block elimination and the matrix inversion lemma

• solving underdetermined equations

Matrix structure and algorithm complexity

cost (execution time) of solving Ax = b with A ∈ Rn×n

• for general methods, grows as n3

• less if A is structured (banded, sparse, Toeplitz, . . . )

flop counts

• flop (floating-point operation): one addition, subtraction,
multiplication, or division of two floating-point numbers

• to estimate complexity of an algorithm: express number of flops as a
(polynomial) function of the problem dimensions, and simplify by

• not an accurate predictor of computation time on modern computers

• useful as a rough estimate of complexity

vector-vector operations (x, y ∈ Rn)

• inner product xT y: 2n -1 flops (or 2n if n is large)

• sum x + y, scalar multiplication x: n flops

matrix-vector product y = Ax with A ∈ Rm×n

• m(2n - 1) flops (or 2mn if n large)

• 2N if A is sparse with N nonzero elements

• 2p(n + m) if A is given as A = UVT , U ∈ Rm×p, V ∈ Rn×p

matrix-matrix product C = AB with A ∈ Rm×n, B ∈ Rn×p

• mp(2n - 1) flops (or 2mnp if n large)

• less if A and/or B are sparse

• (1/2)m(m + 1)(2n - 1) ≈ m2n if m = p and C symmetric

Linear equations that are easy to solve

diagonal matrices lower triangular  called forward substitution

upper triangular flops via backward substitution

orthogonal matrices: A-1 = AT

• 2n2 flops to compute x = AT b for general A

• less with structure, e.g., if A = I - 2uuT with we can
compute x = AT b = b - 2(uT b)u in 4n flops

permutation matrices: where is a permutation of (1, 2, . . . , n)

• interpretation: • satisfies A-1 = AT , hence cost of solving Ax = b is 0 flops
example: ## The factor-solve method for solving Ax = b

• factor A as a product of simple matrices (usually 2 or 3): (Ai diagonal, upper or lower triangular, etc)
• compute by solving k ‘easy’ equations cost of factorization step usually dominates cost of solve step

equations with multiple righthand sides cost: one factorization plus m solves

## LU factorization

every nonsingular matrix A can be factored as
A = PLU

with P a permutation matrix, L lower triangular, U upper triangular
cost: (2/3)n3 flops

Solving linear equations by LU factorization.

given a set of linear equations Ax = b, with A nonsingular.
1. LU factorization. Factor A as A = PLU ((2/3)n3 flops).
2. Permutation. Solve (0 flops).
3. Forward substitution. Solve (n2 flops).
4. Backward substitution. Solve (n2 flops).

cost: (2/3)n3 + 2n2 ≈ (2/3)n3 for large n

sparse LU factorization

A = P1LUP2

• adding permutation matrix P2 offers possibility of sparser L, U (hence,
cheaper factor and solve steps)

• P1 and P2 chosen (heuristically) to yield sparse L, U

• choice of P1 and P2 depends on sparsity pattern and values of A

• cost is usually much less than (2/3)n3; exact value depends in a
complicated way on n, number of zeros in A, sparsity pattern

## Cholesky factorization

every positive definite A can be factored as
A = LLT

with L lower triangular
cost: (1/3)n3 flops

Solving linear equations by Cholesky factorization.

given a set of linear equations Ax = b, with 1. Cholesky factorization. Factor A as A = LLT ((1/3)n3 flops).
2. Forward substitution. Solve (n2 flops).
3. Backward substitution. Solve (n2 flops).

cost: (1/3)n3 + 2n2 ≈ (1/3)n3 for large n

sparse Cholesky factorization

A = PLLTPT

• adding permutation matrix P offers possibility of sparser L

• P chosen (heuristically) to yield sparse L

• choice of P only depends on sparsity pattern of A (unlike sparse LU)

• cost is usually much less than (1/3)n^3; exact value depends in a
complicated way on n, number of zeros in A, sparsity pattern

## LDLT factorization

every nonsingular symmetric matrix A can be factored as

A = PLDLTPT

with P a permutation matrix, L lower triangular, D block diagonal with
1 × 1 or 2 × 2 diagonal blocks

cost: (1/3)n3

• cost of solving symmetric sets of linear equations by LDLT factorization:
(1/3)n3 + 2n2 ≈ (1/3)n3 for large n

• for sparse A, can choose P to yield sparse L; cost ≪ (1/3)n3

## Equations with structured sub-blocks (1)

• variables • if A11 is nonsingular, can eliminate to compute x2, solve Solving linear equations by block elimination.

given a nonsingular set of linear equations (1), with A11 nonsingular.
1. Form and 2. Form 3. Determine x2 by solving 4. Determine x1 by solving dominant terms in flop count

• step 1: (f is cost of factoring A11; s is cost of solve step)

• step 2: (cost dominated by product of A21 and )
• step 3: total: examples

• general no gain over standard method
#flops • block elimination is useful for structured for example, diagonal ## Structured matrix plus low rank term

(A + BC)x = b

• A ∈ Rn×n, B ∈ Rn×p, C ∈ Rp×n

• assume A has structure (Ax = b easy to solve)
first write as now apply block elimination: solve then solve Ax = b − By

this proves the matrix inversion lemma: if A and A + BC nonsingular,
(A + BC)-1 = A-1 - A-1B(I + CA-1B)-1CA-1

example: A diagonal, B,C dense

• method 1: form D = A + BC, then solve Dx = b
cost: (2/3)n3 + 2pn2

• method 2 (via matrix inversion lemma): solve
(I + CA−1B)y = CA-1b, (2)
then compute x = A-1b - A-1By
total cost is dominated by (2): 2p2n + (2/3)p3 (i.e., linear in n)

## Underdetermined linear equations

if A ∈ Rp×n with p < n, rank A = p,  is (any) particular solution
• columns of span nullspace of A
• there exist several numerical methods for computing F
(QR factorization, rectangular LU factorization, . . . )