Try our Free Online Math Solver!

Matrix, Vector Operations
BigO
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 nonnegative functions (otherwise add  . ) to the definitions
• represents an asymptotic upper
bound on f (n) up to a
constant
• example:
BigOmega
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.
BigTheta
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: matrixvector operations, e.g.
• Level 3: matrixmatrix operations, e.g.
• optimized versions of the reference BLAS are used everyday: ATLAS, etc.
vecvec, matvec, matmat
• inner product of u and v both [n
× 1]
• → n multiplies, n  1 additions
• → O(n) flops
• matvec of A ([n × n]) and
u ([n × 1])
• → n^{2} multiplies, n^{2} additions
• → O(n^{2}) flops
• matmat of A ([n
× n]) and B ([n
× n])
• → n^{3} multiplies, n^{3} additions
• → O(n^{3}) flops
matlab test
four tests:
• matrixmatrix multiply
• inner product
• matrixvector multiply
• n matrixvector 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 elementby 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 