# 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])

**
• **→ n

^{2}multiplies, n

^{2}additions

**•**→ O(n

^{2}) flops

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

**• **→ n^{3} multiplies, n^{3} additions

**• **→ O(n^{3}) flops

**matlab test
**four tests:

**•**matrix-matrix multiply

**•**inner product

**•**matrix-vector multiply

**•**n matrix-vector multiplies

order them ...fastest to slowest

**testflop.m**

**• **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 |