UNIT 3 Advanced algorithm

Advanced Algorithms (Osmania University)

 UNIT-3
S.No TOPICS PAGE NO
1 Flow-Networks 81
2 Maxflow-mincut theorem 82
3 Ford-Fulkerson Method to Compute Maximum Flow 85
4 Edmond-Karp Maximum-Flow Algorithm 88
5 Matrix Computations 92
6 Strassen’s Algorithm 93
7 Introduction to Divide and Conquer Paradigm 94
8 Inverse of a Triangular Matrix 97
Relation between the Time Complexities of Basic
9 100
Matrix Operations
10 LUP-Decomposition 102

Page80
FLOW-NETWORKS:
A network is a directed graph G with vertices V and edges E combined with a function cc,
which assigns each edge ee a non-negative integer value, the capacity of ee. Such a network is called
a flow network, if we additionally label two vertices, one as source and one as sink.
A flow in a flow network is function ff, that again assigns each edge ee a non-negative integer
value, namely the flow. The function has to fulfill the following two conditions:
The flow of an edge cannot exceed the capacity.
f(e) ≤ c(e)
And the sum of the incoming flow of a vertex uu has to be equal to the sum of the outgoing flow
of u except in the source and sink vertices.

∑ 𝑓((v, u)) = ∑ 𝑓((u, v))

(v,u)∈E (u,v)∈E
The source vertex ss only has an outgoing flow and the sink vertex tt has only incoming flow.
It is easy to see that the following equation holds:

∑ 𝑓((s, u)) = ∑ 𝑓((u, t))

(s,u)∈E (u,t)∈E
A good analogy for a flow network is the following visualization: We represent edges as water pipes,
the capacity of an edge is the maximal amount of water that can flow through the pipe per second, and
the flow of an edge is the amount of water that currently flows though the pipe per second. This
motivates the first flow condition. There cannot flow more water through a pipe than its capacity. The
vertices act as junctions, where water comes out of some pipes and distributes it in some way to other
pipes. This also motivates the second flow condition. In each junction all the incoming water has to be
distributed to the other pipes. It cannot magically disappear or appear. The source s is origin of all the
water and the water can only drain in the sink t. The following image shows a flow network. The first
value of each edge represents the flow, which is initially 0, and the second value represents the
capacity.

The value of a flow of a network is the sum of all flows that gets produced in source ss, or equivalently
of the flows that are consumed in the sink tt. A maximal flow is a flow with the maximal possible
value. Finding this maximal flow of a flow network is the problem that we want to solve.
In the visualization with water pipes, the problem can be formulated in the following way: how much
water can we push through the pipes from the source to the sink. The following image shows the
Page81
maximal flow in the flow network.

In graph theory, a flow network is defined as a directed graph involving a source(S) and a sink(T) and
several other nodes connected with edges. Each edge has an individual capacity which is the maximum
limit of flow that edge could allow.
Flow in the network should follow the following conditions:
• For any non-source and non-sink node, the input flow is equal to output flow.
• For any edge (Ei) in the network, 0≤flow (Ei) ≤Capacity (Ei).
• Total flow out of the source node = total flow in to the sink node.
• Net flow in the edges follows skew symmetry i.e. F(u,v)=−F(v,u) where F(u,v) is flow from
node u to node v. This leads to a conclusion where you have to sum up all the flows between
two nodes (either directions) to find net flow between the nodes initially.

Maximum Flow:
It is defined as the maximum amount of flow that the network would allow to flow from source to sink.
Multiple algorithms exist in solving the maximum flow problem. Two major algorithms to solve these
kind of problems are Ford-Fulkerson algorithm and Dinic's Algorithm.

MAXFLOW-MINCUT THEOREM:
In computer science and optimization theory, the max-flow min-cut theorem states that in a flow
network, the maximum amount of flow passing from the source to the sink is equal to the total weight
of the edges in the minimum cut, i.e the smallest total weight of the edges which if removed would
disconnect the source from the sink.

Find minimum s-t cut in a flow network

In a flow network, an s-t cut is a cut that requires the source ‘s’ and the sink ‘t’ to be in different subsets
and it consists of edges going from the source’s side to the sink’s side. The capacity of an s-t cut is
defined by the sum of the capacity of each edge in the cut-set. The problem discussed here is to find
minimum capacity s-t cut of the given network. Expected output is all edges of the minimum cut.
For example, in the following flow network, example s-t cuts are {{0 ,1}, {0, 2}}, {{0, 2}, {1, 2}, {1,
3}}, etc. The minimum s-t cut is {{1, 3}, {4, 3}, {4 5}} which has capacity as 12+7+4 = 23.

Page82
Minimum Cut and Maximum Flow
Maximum Bipartite Matching, this is another problem which can be solved using Ford-
Fulkerson Algorithm. This is based on max-flow min-cut theorem. The max-flow min-cut
theorem states that in a flow network, the amount of maximum flow is equal to capacity of the
minimum cut. From Ford-Fulkerson, we get capacity of minimum cut. How to print all edges that form
the minimum cut? The idea is to use residual graph.
Following are steps to print all edges of the minimum cut.
1. Run Ford-Fulkerson algorithm and consider the final residual graph.
2. Find the set of vertices that are reachable from the source in the residual graph.
3. All edges which are from a reachable vertex to non-reachable vertex are minimum cut edges.
Print all such edges.

Example: Finding the Minimum Cut

The final residual graph is used to find the minimum cut. First, you find all nodes reachable from the
source in the residual graph. This is one set of nodes, which we color purple below:

Now, in the original graph, we divide our nodes into two sets: the set determined above, and all of the
remaining nodes. They are drawn purple and yellow in the original graph below:

Page83
The minimum cut is composed of all the edges that go from the source set to the sink set. These are
edges AD, CD and EG, which I've drawn in red above. The sum of their capacities equals the maximum
flow of six.

Example: Finding the Maximum Flow Path through the Graph

Instead of using a depth-first search, you can use a modification of Dijkstra's algorithm to find the path
through the residual that has the maximum flow. When processing a node, Dijkstra's algorithm traverses
the node's edges, and if shorter paths to any other nodes is discovered, the nodes are updated. At each
step, the node with the shortest known path is processed next.

The modification works as follows. When processing a node, again the algorithm traverses the node's
edges, and if paths with more flow to any other nodes are discovered, then the nodes are updated. At
each step, the node with the maximum flow is processed next.

We'll work an example with the same graph as above:

The maximum flow path here is A->D->F->G with a flow of three:

Flow Residual

Page84
The next maximum flow path is A->B->C->D->F->G with a flow of 2:

Residual
Flow

The final path is A->B->C->E->G with a flow of one:

Residual
Flow

FORD-FULKERSON METHOD TO COMPUTE MAXIMUM FLOW

The Concept of Residual Graph is needed for understanding the implementation.
Residual Graph of a flow network is a graph which indicates additional possible flow. If there is a path
from source to sink in residual graph, then it is possible to add flow. Every edge of a residual graph has
a value called residual capacity which is equal to original capacity of the edge minus current flow.
Residual capacity is basically the current capacity of the edge.
Let us now talk about implementation details. Residual capacity is 0 if there is no edge between two
vertices of residual graph.

➢ We can initialize the residual graph as original graph as there is no initial flow and initially residual
capacity is equal to original capacity. To find an augmenting path, we can either do a BFS or DFS of
the residual graph. We have used BFS in below implementation.

➢ Using BFS, we can find out if there is a path from source to sink. BFS also builds parent [ ] array.
Using the parent [ ] array, we traverse through the found path and find possible flow through this

Page85
 path by finding minimum residual capacity along the path. We later add the found path flow to
overall flow.

➢ The important thing is, we need to update residual capacities in the residual graph. We subtract path
flow from all edges along the path and we add path flow along the reverse edges. We need to add
path flow along reverse edges because may later need to send flow in reverse direction

A demonstration of working of Ford-Fulkerson algorithm is shown below with the help of diagrams.

Page86
 No more Path Left Max Flow : 15

Implementation:
• An augmenting path in residual graph can be found using DFS or BFS.
• Updating residual graph includes following steps: (refer the diagrams for better understanding)
o For every edge in the augmenting path, a value of minimum capacity in the path is
subtracted from all the edges of that path.
o An edge of equal amount is added to edges in reverse direction for every successive
nodes in the augmenting path.
The complexity of Ford-Fulkerson algorithm cannot be accurately computed as it all depends on the
path from source to sink. For example, considering the network shown below, if each time, the path
chosen are S−A−B−T and S−B−A−T alternatively, then it can take a very long time. Instead, if path
chosen are only S−A−T and S−B−T, would also generate the maximum flow.

Example- Ford-Fulkerson algorithm:

Each Directed Edge is labeled with capacity. Use the Ford-Fulkerson algorithm to find the maximum
flow.

The left side of each part shows the residual network Gf with a shaded augmenting path p,and the right
side of each part shows the net flow f.

Page87
EDMOND-KARP MAXIMUM-FLOW ALGORITHM:
Edmonds–Karp algorithm is an implementation of the Ford–Fulkerson method for computing
the maximum flow in a flow network in much more optimized approach. Edmonds-Karp is identical to
Ford-Fulkerson except for one very important trait. The search order of augmenting paths is well
defined. Here augmenting paths, along with residual graphs, are the two important concepts to
understand when finding the max flow of a network.

Page88
Edmonds–Karp algorithm
Algorithm EdmondsKarp(G)
1: f ← 0; Gf ← G
2: while Gf contains an s − t path P do
3: Let P be an s − t path in Gf with the minimum number of edges.
4: Augment f using P.
5: Update Gf
6: end while
7: return f
Augmenting paths are simply any path from the source to the sink that can currently take more flow.
Over the course of the algorithm, flow is monotonically increased. So, there are times when a path from
the source to the sink can take on more flow and that are an augmenting path. This can be found by a
breadth-first search, as we let edges have unit length. The running time of O(V E2) is found by showing
that each augmenting path can be found in O(E) time, that every time at least one of the E edges
becomes saturated (an edge which has the maximum possible flow), that the distance from the saturated
edge to the source along the augmenting path must be longer than last time it was saturated and that the
length is at most V. Another property of this algorithm is that the length of the shortest augmenting path
increases monotonically.

Page89
Notice how the length of the augmenting path found by the algorithm (in red) never decreases. The
paths found are the shortest possible. The flow found is equal to the capacity across the minimum cut in
the graph separating the source and the sink. There is only one minimal cut in this graph, partitioning
the nodes into the sets { A , B , C , E } and { D , F , G }, with the capacity is c(A,D) + c (C,D) +c (E,G)
=3+1+1 =5

Complexity
➢ Worst case time complexity: Θ(V * E * E)
➢ Average case time complexity: Θ(V * E * E)
➢ Best case time complexity: Θ(V * E * E)
➢ Space complexity: Θ(E + V)

Proof of complexity: 2 Key ideas:

➢ In the residual network, the distance of any vertex from the source never decreases during the
algorithm.
➢ Any edge can become critical at most O(V) times.

Applications of Edmonds Karp Algorithm are:

➢ Finding the maximum flow in a flow network
➢ Maximizing the transportation with given traffic limits
➢ Maximizing packet flow in computer networks.

Example: Edmonds-Karp: Finding the minimum hop path

Finally, the Edmonds-Karp algorithm uses a straightforward breadth-first search to find the minimum
hop path through the residual graph. This is equivalent to treating the residual as an unweighted and
performing a shortest path search on it.

Again, we use the same graph as an example:

There are two minimum hop paths: A->D->E->G and A->D->F->G. Suppose we process the former of
these, with a flow of one:

Page90
 Flow Residual

Now, there is only one minimum hop path through the residual: A->D->F->G, with a flow of two:

Flow Residual

At this point, there are only two paths through the residual: A->B->C->D->F->G and A->B->C->E-
>D->F->G. The first of these has fewer hops, so we process it. It has a flow of two:

Flow Residual

The final path through the residual is A->B->C->E->D->F->G with a flow of one. When we process
it, we get the same flow and residual graphs as the other two algorithms:

Flow Residual

Page91
MATRIX COMPUTATIONS:
A matrix is a rectangular array of numbers arranged in rows and columns. The array of numbers below
is an example of a matrix. The number of rows and columns that a matrix has is called its dimension
or its order. By convention, rows are listed first; and columns, second

Use of Matrix Computation:

They are used for plotting graphs, statistics and also to do scientific studies and research in almost
different fields. Matrices are also used in representing the real world data's like the population of
people, infant mortality rate, etc. They are best representation methods for plotting surveys.
Matrix Multiplication:

Standard algorithm:

Idea of Strassen’s Algorithm:

Page92
STRASSEN’S ALGORITHM:
1. Divide: Partition A and B into (n/2)x(n/2) submatrices. Form terms to be multiplied using + and –.
2. Conquer: Perform 7 multiplications of (n/2)x(n/2) submatrices recursively.
3. Combine: Perform +and – on (n/2)x(n/2) submatrices. Combine the result of two matrices to find
the final product or final matrix.

In this context, using Strassen’s Matrix multiplication algorithm, the time consumption can be
improved a little bit. Strassen’s Matrix multiplication can be performed only on square
matrices where n is a power of 2. Order of both of the matrices are n × n.
Divide X, Y and Z into four (n/2)×(n/2) matrices as represented below −
𝐼 𝐽 𝐴 𝐵 𝐸 𝐹
Z=[ ] X= [ ] Y=[ ]
𝐾 𝐿 𝐶 𝐷 𝐺 𝐻
Using Strassen’s Algorithm compute the following:
M1:=(A+C)×(E+F)
M2:=(B+D)×(G+H)
M3:=(A−D)×(E+H)
M4:=A×(F−H)
M5:=(C+D)×(E)
M6:=(A+B)×(H)
M7:=D×(G−E)
Then,
I:=M2+M3−M6−M7
J:=M4+M6
K:=M5+M7
L:=M1−M3−M4−M5
Analysis
c n
T (n) = { + 𝑑𝑥𝑛2𝑖𝑓𝑛 = 1 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒where c and d are constants
7xT( )
2
➢ Using this recurrence relation, we get T(n)=O(nlog7)T(n)=O(nlog7)
➢ Addition and Subtraction of two matrices takes O(N2) time. So time complexity can be written
asT(N) =7T (N/2) + O (N2)
➢ Hence, the complexity of Strassen’s matrix multiplication algorithm is O(nlog7)

Page93
 ➢ The number 2.81 may not seem much smaller than 3, but because the difference is in the
exponent, the impact on running time is significant. In fact, Strassen’s algorithm beats the
ordinary algorithm today’s machines for n  30 so on.

Generally Strassen’s Method is not preferred for practical applications for following reasons.

1. The constants used in Strassen’s method are high and for a typical application Naive method works
better.
2. For Sparse matrices, there are better methods especially designed for them.
3. The submatrices in recursion take extra space.
4. Because of the limited precision of computer arithmetic on noninteger values, larger errors
accumulate in Strassen’s algorithm than in Naive Method

INTRODUCTION TO DIVIDE AND CONQUER PARADIGM:

Divide and Conquer is an algorithmic pattern. In algorithmic methods, the design is to take a dispute on
a huge input, break the input into minor pieces, decide the problem on each of the small pieces and then
merge the piecewise solutions into a global solution. This mechanism of solving the problem is called
the Divide & Conquer Strategy.

Divide and Conquer algorithm consists of a dispute using the following three steps.
1. Divide: The original problem into a set of sub-problems.
2. Conquer: Solve every sub-problem individually, recursively.
3. Combine: Put together the solutions of the sub-problems to get the solution to the whole
problem.

Page94
Fundamental of Divide & Conquer Strategy:
There are two fundamentals of Divide & Conquer Strategy:
1. Relational Formula
2. Stopping Condition
1. Relational Formula: It is the formula that we generate from the given technique. After generation of
Formula we apply D&C Strategy, i.e. we break the problem recursively & solve the broken sub-
problems.
2. Stopping Condition: When we break the problem using Divide & Conquer Strategy, then we need
to know that for how much time, we need to apply divide & Conquer. So the condition where we need
to stop our recursion steps of D&C is called as Stopping Condition.

Standard Algorithms based on divide and conquer

The following algorithms are based on divide and conquer design paradigm
➢ Binary Search
➢ Strassen's matrix multiplication
➢ Closestpair(points)
➢ Cooley-Tukey Fast Fourier Transform (FFT) Algorithm
➢ Karatsuba Algorithm for Fast Multiplication
➢ Maximum and Minimum Problem
➢ Sorting (merge sort, quick sort)
➢ Tower of Hanoi.

Divide and Conquer

Following is simple Divide and Conquer method to multiply two square matrices.
1) Divide matrices A and B in 4 sub-matrices of size N/2 x N/2 as shown in the below diagram.
2) Calculate following values recursively. ae + bg, af + bh, ce + dg and cf + dh.

In the above method, we do 8 multiplications for matrices of size N/2 x N/2 and 4 additions. Addition
of two matrices takes O(N2) time. So the time complexity can be written asT(N) = 8T (N/2) + O (N2)
From Master’s Theorem, time complexity of above method is O (N3)

Simple Divide and Conquer also leads to O(N3), can there be a better way?
In the above divide and conquer method, the main component for high time complexity is 8 recursive
calls. The idea of Strassen’s method is to reduce the number of recursive calls to 7. Strassen’s method
is similar to above simple divide and conquer method in the sense that this method also divide matrices

Page95
to sub-matrices of size N/2 x N/2 as shown in the below diagram, but in Strassen’s method, the four
sub-matrices of result are calculated using following formulae.

Analysis of Divide and Conquer Algorithm:

Pros of Divide and Conquer Strategy

1. Solves difficult problems with ease.
2. Algorithms designed with Divide and Conquer strategies are efficient when compared to its
counterpart Brute-Force approach for e.g. if we compare time complexity of simple matrix
multiplication i.e. O(n3) and that of Strassen's matrix multiplication i.e. O(n2.81).
3. Algorithms designed under Divide and Conquer strategy does not require any modification as
they inhibit parallelism and can easily be processed by parallel processing systems.
4. It makes efficient use of memory cache. This happens so because that problems when divided
gets so small that they can be easily solved in the cache itself.
5. If we use floating numbers then the results may improve since round off control is very efficient
in such algorithms.
6. The most recognizable benefit of the divide and conquer paradigm is that it allows us to solve
difficult problem, such as the Tower of Hanoi, which is a mathematical game or puzzle. Being
given a difficult problem can often be discouraging if there is no idea how to go about solving it.
However, with the divide and conquer method, it reduces the degree of difficulty since it divides
the problem into sub-problems that are easily solvable and usually runs faster than other
algorithms would.

Page96
 7. It also uses memory caches effectively. When the sub-problems become simple enough, they
can be solved within a cache, without having to access the slower main memory.

Cons of Divide and Conquer Strategy

1. Divide and Conquer strategy uses recursion that makes it a little slower and if a little error
occurs in the code the program may enter into an infinite loop.
2. Usage of explicit stacks may make use of extra space.
3. If performing a recursion for number of times greater than the stack in the CPU than the system,
may crash.
4. Choosing base cases is also a limitation as picking small cases may work, if the cases are taken
much higher than the capacity of the system than problems may occur.
5. Sometimes a case where the problem when broken down results in same sub-problems which
may needlessly increase the solving time and extra space may be consumed.
6. One of the most common issues with this sort of algorithm is the fact that the recursion is slow,
which in some cases outweighs any advantages of this divide and conquer process.
7. Sometimes it can become more complicated than a basic iterative approach, especially in cases
with a large n. In other words, if someone wanted to add a large amount of numbers together, if
they just create a simple loop to add them together., it would turn out to be a much simpler
approach than it would be to divide the numbers up into two groups, add these groups
recursively and then add the sums of the two groups together.

INVERSE OF A TRIANGULAR MATRIX:

➢ Computation of inverse using co-factor matrix

➢ Properties of the inverse of a matrix

➢ Inverse of special matrices

✓ Unit Matrix
✓ Diagonal Matrix
✓ Orthogonal Matrix
✓ Lower/Upper Triangular Matrices

Matrix Inverse
➢ Inverse of a matrix can only be defined for square matrices.
➢ Inverse of a square matrix exists only if the determinant of that matrix is non-zero.
➢ Inverse matrix of 𝐴 is noted as 𝐴−1.
➢ 𝐴𝐴−1 = 𝐴−1𝐴 = I

Page97
Inverse of a 3 x 3 matrix (using cofactor matrix):
Calculating the inverse of a 3 × 3 matrix is:
• Compute the matrix of minors for A.
• Compute the cofactor matrix by alternating + and – signs.
• Compute the adjugate matrix by taking a transpose of cofactor matrix.
• Divide all elements in the adjugate matrix by determinant of matrix.

Properties of Inverse of a Matrix

Inverse of Identity matrices

• Inverse of identity matrix is itself.
• Because: • 𝐼𝐼 = I
Example:

Inverse of a 3 x 3 matrix (using cofactor matrix)

Page98
Inverse of Diagonal matrices
• The determinant of a diagonal matrix is the product of its diagonal elements.
• If they all are non-zero, then determinant is non-zero and the matrix is invertible.
• The inverse of a diagonal matrix A is another diagonal matrix B whose diagonal elements are the
reciprocals of the diagonal elements of A.
• Example:

Inverse of Orthonormal matrices

➢ Earlier, we saw that multiplication of an orthogonal (orthonormal) matrix in its transpose results in
identity matrix
➢ If 𝐴 is an orthonormal matrix, its inverse is equal to its transpose
➢ 𝐴 is an orthonormal 𝑛 × 𝑛 matrix
➢ Recall 𝐴𝐴𝑇= 𝐼𝑛 , where 𝐼𝑛 is a 𝑛 × 𝑛 identity matrix
➢ So, 𝐴𝑇 = 𝐴−1

Inverse of Upper/Lower Triangular Matrices

➢ Inverse of an upper/lower triangular matrix is another upper/lower triangular matrix.
➢ Inverse exists only if none of the diagonal element is zero.
➢ Can be computed from first principles: Using the definition of an Inverse. 𝐴𝐴−1 = 𝐼. No need to
compute determinant. Diagonal elements of 𝐴−1 is the reciprocal of the elements of 𝐴.
➢ Other elements are iteratively computed such that the product of the matrices is 𝐼.

Page99
Inverse of Upper/Lower Triangular Matrices

RELATION BETWEEN THE TIME COMPLEXITIES OF BASIC

MATRIX OPERATIONS:
A matrix is a rectangular or square grid of numbers arranged into rows and columns. Each
number in the matrix is called an element, and they are arranged in what is called an array. The plural of
“matrix” is “matrices”. Matrices are often used in algebra to solve for unknown values in linear
equations, and in geometry when solving for vectors and vector operations.

The four "basic operations" on numbers are addition, subtraction, multiplication, and division.
For matrices, there are three basic row operations; that is, there are three procedures that you can do
with the rows of a matrix.
Basic Arithmetic Operations
Operation Input Output Algorithm Complexity
Two n-digit One n+1-digit Basic addition with
Addition Θ(n), Θ(log(N))
numbers N, N number carry
Two n-digit One n+1-digit Basic subtraction
Subtraction Θ(n), Θ(log(N))
numbers N, N number with borrow
Two n-digit One 2n-digit Basic long
Multiplication O(n2)
numbers number multiplication
Karatsuba algorithm O(n1.585)
3-way Toom–Cook
O(n1.465)
multiplication
k-way Toom–Cook O(nlog (2k −
multiplication 1)/log k)
Mixed-level Toom–
O(n 2√2
Cook (Knuth 4.3.3-
log n log n)
T)[2]

Page100
 Schönhage–Strassen
O(n log n log log n)
algorithm
Fürer's algorithm[3] O(n log n 22 log* n)
Harvey-Hoeven
O(n log n)
algorithm[4] [5]
Two n-digit One n-digit
Division Basic long division O(n2)
numbers number
Burnikel-Ziegler
Divide-and-Conquer O(M(n) log n)
Division [6]
Newton–Raphson
O(M(n))
division
One n-digit One n-digit
Square root Newton's method O(M(n))
number number
Two n-digit Repeated
Modular One n-digit
integers and a k- multiplication and O(M(n) 2k)
exponentiation integer
bit exponent reduction
Exponentiation by
O(M(n) k)
squaring
Exponentiation
with Montgomery O(M(n) k)
reduction
Matrix Algebric Function
Operation Input Output Algorithm Complexity
Basic matrix
O(n3)
multiplication
Strassen algorithm O(n2.807)
Matrix
Two n×n matrices One n×n matrix Coppersmith–
multiplication O(n2.376)
Winograd algorithm
Optimized CW-like
O(n2.373)
algorithms
One n×m matrix
Matrix Schoolbook matrix
& One n×p matrix O(nmp)
multiplication multiplication
one m×p matrix
One n×⌈n⌉ matrix O(nω(k)+∈)where
Matrix
& One n×n matrix Algorithms upper bounds on
multiplication
one ⌈n⌉×n matrix ω(k)
Matrix Gauss–Jordan
One n×n matrix One n×n matrix O(n3)
inversion* elimination

Page101
 Strassen algorithm O(n2.807)
Coppersmith–
O(n2.376)
Winograd algorithm
Optimized CW-like
O(n2.373)
algorithms
One m×m matrix,
one m×n matrix, Bidiagonalizationand O(mn2 + m2 n)
& QR algorithm (m ≥ n)
Singular value one n×n matrix
One m×n matrix
decomposition One m×n matrix,
one n×n matrix, Bidiagonalization O(mn2)
& and QR algorithm (m ≥ n)
one n×n matrix
Laplace expansion O(n!)
Division-free
O(n4)
algorithm
Determinant One n×n matrix One number LU decomposition O(n3)
Bareiss algorithm O(n3)
Fast matrix
O(n2.373)
multiplication
Back
Triangular matrix n solutions Back substitution O(n2)
substitution

LUP-DECOMPOSITION:

Definition:
A m×n matrix is said to have a LU-decomposition if there exists matrices L and U with the
following Properties:
(i) L is a m×n lower triangular matrix with all diagonal entries being 1.
(ii) U is a m×n matrix in some echelon form.
(iii) A = LU.

Advantages of LU-Decomposition:
Suppose we want to solve a m×n system AX = b.
If we can find a LU-decomposition for A , then to solve AX =b, it is enough to solve the systems

Page102
Thus the system LY = b can be solved by the method of forward substitution and the system UX = Y
can be solved by the method of backward substitution. The following examples will illustrate this.
Example:
Consider the given system AX = b, where

It is easy to check that A = LU, where

Thus, to solve AX = b, we first solve LY = b by forward substitution

to get

Now, we solve UX =Y by backward substitution:

and get

The above discussion raises the following question. Which matrices have LU-decomposition, and how
to find them? The answer is given by the following:
Theorem:
Let A be a m×n matrix and , ,... be elementary matrices such that
U = ............. A
is in non-echelon form. If none of the 's corresponds to the operation of row interchange, then

Page103
C= ... is a lower triangular invertible matrix. Further L = is also a lower triangular
matrix with A = LU .
Example:
Let

Then the row operation -2 + ,3 + , + give

The corresponding elementary matrices and their inverses are

Thus

Let us observe that for

Page104
Note that the element below the main diagonal in L is the pivotal columns are the negatives of the
scalars used in the respective column to make all the entries in that column below the pivot zero.
For example, in first column, we operated -2 + and 3 + . Thus, in the first column, the second
entry is 2 and the third entry is -3.

Example:
Let

To reduce A to a row -echelon form, we operate ½ + and ½ + for the first pivotal columns,
namely the second column to get

Next we operate -3 + for the next pivotal column, the column to get

This has only two non-zero rows. Thus L is given by replacing entries below diagonal pivotal columns
by -ve of the multiples: in column 1 these are -½ , -½ ,and in second column this is 3. Thus

Let us check

Page105
The method followed in examples can in fact be proved mathematically as follows:

Theorem:

Let be the m m elementary matrix which corresponds to the elementary row operation of

multiplying the ith row by the scalar - and adding it to the jth row. Then

(iii) If is such that

Page106
 is in non-echelon form, then

Till now we had assumed that no row interchanges were required to transform A to upper triangular
form. If such row operations are needed we can proceed by the following:

Theorem
Let A be an m n matrix which requires row interchanges , in addition to the
other elementary row operations to transform it to row echelon form U : Then , the matrix
PA requires no row interchanges to reduce it to row echelon form and hence can be written
as PA = LU .
The system AX = b is equivalent to a system PAX = Pb , Where PA has LU-decomposition .
Definition
A m×m matrix which arises from by finite number of row interchanges is called
a permutation matrix.

Example:

To continue we need to interchange to get

Page107
and now U is in r.e.f..
Thus, we consider PA and transform it to r.e.f

Hence,

Page108