Matrix, Vector Operations

Big-O

How to measure the impact of n on algorithmic cost?

Let g(n) be a function of n. Then define

That is, if there is a constant c such that 0 ≤  f (n) ≤ cg(n) is
satisfied.
assume non-negative functions (otherwise add | . |) to the definitions
represents an asymptotic upper bound on f (n) up to a
constant
example:

Big-Omega
asymptotic lower bound

Let g(n) be a function of n. Then define

That is, if there is a constant c such that 0 ≤ cg(n) ≤ f (n) is
satisfied.

Big-Theta
asymptotic tight bound

Let g(n) be a function of n. Then define

Equivalently,

BLAS
Basic Linear Algebra Subprograms (BLAS) interface introduced APIs for
common linear algebra tasks
Level 1: vector operations (dot products, vector norms, etc) e.g.

Level 2: matrix-vector operations, e.g.

Level 3: matrix-matrix operations, e.g.

optimized versions of the reference BLAS are used everyday: ATLAS, etc.

vec-vec, mat-vec, mat-mat

inner product of u and v both [n × 1]

→ n multiplies, n - 1 additions
→ O(n) flops

mat-vec of A ([n × n]) and u ([n × 1])

→ n2 multiplies, n2 additions
→ O(n2) flops

mat-mat of A ([n × n]) and B ([n × n])

→ n3 multiplies, n3 additions
→ O(n3) flops

matlab test
four tests:
matrix-matrix multiply
inner product
matrix-vector multiply
n matrix-vector multiplies
order them ...fastest to slowest
testflop.m

Gaussian Elimination

Solving Diagonal Systems
Solving Triangular Systems
Gaussian Elimination Without Pivoting
> Hand Calculations
>Cartoon Version
> The Algorithm
Gaussian Elimination with Pivoting
> Row or Column Interchanges, or Both
> Implementation
Solving Systems with the Backslash Operator

Solving Diagonal Systems
The system defined by

is equivalent to

The solution is

Listing 1: Diagonal System Solution


In Matlab:
1 >> A = ... % A is a diagonal matrix
2 >> b = ...
3 >> x = b./diag(A)

This is the only place where element-by- element division (. /) has anything to
do with solving linear systems of equations.

Operations?
Try...
Sketch out an operation count to solve a diagonal system of equations...

cheap!
one division n times FLOPS

Triangular Systems
The generic lower and upper triangular matrices are

and

The triangular systems
Ly = b Ux = c

are easily solved by forward substitution and backward substitution,
respectively

Solving Triangular Systems

is equivalent to

Solve in backward order (last equation is solved first)

Solving for for a lower triangular system is called forward
substitution.

Using forward or backward substitution is sometimes referred to as performing
a triangular solve.

Operations?

Try...
Sketch out an operation count to solve a triangular system of equations...

cheap!
begin in the bottom corner: 1 div
row -2: 1 mult, 1 add, 1 div, or 3 FLOPS
row -3: 2 mult, 2 add, 1 div, or 5 FLOPS
row -4: 3 mult, 3 add, 1 div, or 7 FLOPS
...
row -j: about 2j FLOPS
Total FLOPS? FLOPS

Prev Next