Divide and conquer

Divide and conquer is an effective algorithm design technique for solving general
problems.
In this paradigm, the problem is divided into its subproblems. Then the subproblems are
solved recursively or iteratively, and their results are combined to get the final solution of a
given problem.
This is a popular algorithm design paradigm and is used for solving many interesting
problems in the computer science domain.

Examples of Divide and Conquer Algorithms

1. Merge Sort: This sorting algorithm divides the array into halves, sorts each half, and t
hen merges the sorted halves back together.
2. Quick Sort: Similar to merge sort, quick sort selects a pivot element, partitions the arr
ay into elements less than and greater than the pivot, and recursively sorts the partitio
ns.
3. Binary Search: This algorithm searches for a target value in a sorted array by repeate
dly dividing the search interval in half.
4. Matrix Multiplication: Algorithms like Strassen's algorithm use divide and conquer t
o multiply matrices more efficiently than the standard approach.

Divide-and-conquer recurrences are always given in the following form:

Advantages and Disadvantages
Advantages:
 Efficiency: Many divide and conquer algorithms have better time complexity compar
ed to their naive counterparts.
 Parallelism: The independent nature of subproblems allows for parallel processing, i
mproving performance on multi-core systems.
Disadvantages:
 Overhead: The recursive nature can introduce overhead due to function calls and me
mory usage.
 Complexity: Designing divide and conquer algorithms can be complex, especially in
ensuring that the combine step is efficient.
STRASSEN MATRIX MULTIPLICATION
Let there be two matrices A and B of dimensions n × n.
Let C = A × B be the product of two matrices A and B. T
hen the elements of the resultant product matrix Cij are given as follows.

MatrixMultiplication(A, B, m, n, p)
for i = 1 to m
for j = 1 to p
C[i][j] = 0
for k = 1 to n
C[i][j] = C[i][j] + A[i][k] * B[k][j]
return C
If A , B square matrices of size n × n:
3
Time Complexity: O( n )
Strassen's Matrix Multiplication is the divide and conquer approach to solve the matrix
multiplication problems.
Using algebra techniques, Volker Strassen reduced the number of multiplications from 8 to 7.
The reduction of one multiplication provided a faster matrix multiplication algorithm.
 n n
For two n × nmatrices (assume n is even) split them into four × blocks:
2 2
A11 A12 B B12
A=[ ], B=[ 11 ]
A21 A 22 B21 B22

The product blocks are computed by the standard block formula (no Strassen trick):
C 11 ¿ A11 B11 + A12 B 21
C 12 ¿ A 11 B12+ A 12 B 22
C 21 ¿ A 21 B11 + A 22 B 21
C 22 ¿ A 21 B12+ A 22 B22

This uses 8 recursive multiplications of (n /2)×(n/2)matrices and a few additions. That’s

the divide-and-conquer (standard) method.
Let both A and B are t 4×4 matrices:
a 11 a12 a13 a14 b11 b12 b13 b14
a a22 a23 a24 b b 22 b23 b24
A=[ 21 ], B=[ 21 ]
a 31 a32 a33 a34 b 31 b32 b33 b34
a 41 a42 a43 a44 b 41 b 42 b43 b44

Divide Step
We divide each 4×4 matrix into four 2×2 submatrices:
matrices:
a 11 a12 a13 a14
a a22 a23 a24
A=[ 21 ],
a 31 a32 a33 a34
a 41 a42 a43 a44

b11 b 12 b 13 b14
b b 22 b 23 b24
B=[ 21 ]
b31 b 32 b 33 b34
b41 b 42 b 43 b 44

where each block is:

 a11 a12 a13 a14
A 11 ¿[ ], A12 ¿[ ],
a21 a22 a23 a24
a a32 a a34
A21 ¿ [ 31 ], A22 ¿ [ 33 ].
a41 a42 a43 a44

Using the Strassen algorithm, the multiplication of 2 × 2 matrices A and B to yield matrix C
can be carried out using seven multiplications, with the help of the following formulas:

Let matrices A and Bbe divided as:

A11 A12 B B12
A=[ ], B=[ 11 ]
A21 A 22 B21 B22

Define the 7 products:

P1 = (A11 + A22) * (B11 + B22)
P2 = (A21 + A22) * B11
P3 = A11 * (B12 - B22)
P4 = A22 * (B21 - B11)
P5 = (A11 + A12) * B22
P6 = (A21 - A11) * (B11 + B12)
P7 = (A12 - A22) * (B21 + B22)
Compute the Resulting Submatrices:
C11 = P1 + P4 - P5 + P7
C12 = P3 + P5
C21 = P2 + P4
C22 = P1 + P3 - P2 + P6

The resultant matrix C is given as follows:

C = [ P1 + P4 - P5 + P7 P3 + P5
P2 + P4 P1 + P3 - P2 + P6 ]
  Srassen’s method reduces the number of multiplications required for matrix
multiplication.
Instead of performing eight multiplications, Strassen performs only seven
multiplications, but uses additional additions and subtractions.
 Since multiplication is computationally more expensive than addition, this reduction
results in faster matrix multiplication.
 Strassen’s method also fits naturally into the divide-and-conquer technique.

Algorithm Steps:
Step 1:Recursively divide an n × nmatrix into smaller matrices until matrices of size 2 ×2are
obtained.
Step 2:Apply Strassen’s seven formulas to multiply the 2 ×2matrices.
Step 3 Combine the resulting submatrices to form the final product matrix.
Algorithm:
Algorithm: Strassen_Multiply(A, B, n)
Input:
A, B – two n × n matrices
Output:
C – product matrix (A × B)
Begin
If n ≤ threshold then
Compute C = A × B using the conventional method
Else
// Step 1: Partition matrices A and B
Split A into: A11, A12, A21, A22
Split B into: B11, B12, B21, B22

// Step 2: Compute the seven Strassen products

P1 = Strassen_Multiply(A11 + A22, B11 + B22)
P2 = Strassen_Multiply(A21 + A22, B11)
P3 = Strassen_Multiply(A11, B12 − B22)
P4 = Strassen_Multiply(A22, B21 − B11)
P5 = Strassen_Multiply(A11 + A12, B22)
P6 = Strassen_Multiply(A21 − A11, B11 + B12)
 P7 = Strassen_Multiply(A12 − A22, B21 + B22)

// Step 3: Combine to form submatrices of C

C11 = P1 + P4 − P5 + P7
C12 = P3 + P5
C21 = P2 + P4
C22 = P1 + P3 − P2 + P6

// Step 4: Form the final matrix C

C = [ C11 C12
C21 C22 ]
End If
Return C
End
Complexity:

EX:

A11 = [ [1 2]
[3 4] ]
A12 = [ [0 1]
[1 2] ]

A21 = [ [0 1]
[1 0] ]

A22 = [ [2 1]
[1 2] ]

B11 = [ [2 0]
[1 2] ]

B12 = [ [1 1]
[0 1] ]

B21 = [ [0 1]
[1 1] ]

B22 = [ [2 0]
[0 2] ]
Compute the seven Strassen products (copy-friendly):

makefile
Copy code
P1 = (A11 + A22) * (B11 + B22)
= [ [15 12]
[22 24] ]

P2 = (A21 + A22) * B11

 = [ [6 4]
[6 4] ]

P3 = A11 * (B12 - B22)

= [ [-1 -1]
[-3 -1] ]

P4 = A22 * (B21 - B11)

= [ [-4 1]
[-2 -1] ]

P5 = (A11 + A12) * B22

= [ [2 6]
[8 12] ]

P6 = (A21 - A11) * (B11 + B12)

= [ [-4 -4]
[-10 -14] ]

P7 = (A12 - A22) * (B21 + B22)

= [ [-4 -2]
[ 0 0] ]
Form the four result blocks using P1..P7:
C11 = P1 + P4 - P5 + P7
= [ [5 5]
[12 11] ]

C12 = P3 + P5
= [ [1 5]
 [5 11] ]

C21 = P2 + P4
= [ [2 5]
[4 3] ]

C22 = P1 + P3 - P2 + P6
= [ [4 3]
[3 5] ]
Combine the blocks to get final 4×4 matrix C:

markdown
Copy code
C = [ C11 C12
C21 C22 ]

=[[5 5 1 5]
[12 11 5 11 ]
[2 5 4 3]
[4 3 3 5]]
Chain matrix multiplication
Matrix Chain Multiplication (MCM) is a classical optimization problem.
The goal is to find the most efficient way to parenthesize a chain of matrices so that the total
number of scalar multiplications is minimized.
Problem:
the chain matrix multiplication problem can be stated formally as follows:
Given a set of matrices { A 1 , A2 , … , A n } with dimensions { p 0 × p 1 , p1 × p2 , … , p n−1 × p n },
find the optimal order of multiplication such that the total cost of scalar multiplications is
minimized.
For a given set of matrices { A 1 , A2 , … , A n } , determine how the matrices should be
parenthesized to achieve this optimal cost.
To do so, we must first identify all possible ways of parenthesizing the product sequence.
• The matrix multiplication is associative(AB)C = A(BC), but not commutative(AB ≠ BA).
• ((AB)(CD)) = (A(B(CD))),
.
• BUT : ((AB)(CD)) ≠ ((BA)(DC)
Example: consider the chain A1, A2, A3, A4 of 4 matrices– Let us compute the product
A1A2A3A4
There are 5 possible ways:
1. (A1(A2(A3A4)))
2. (A1((A2A3)A4))
3. ((A1A2)(A3A4))
4. ((A1(A2A3))A4)
5. (((A1A2)A3)A4)
If you have “n” matrices

Using the dynamic programming concept, one can split the given matrices into two parts
using the variable k as {A1, A2, …, Ak} and {Ak+1, A2, …, An}. The first partition can be
parenthesized in k ways and the second partition in n − k ways.
Dynamic Programming Approach for Solving Chain Matrix Multiplication Problem
In the chain matrix multiplication problem, our goal is to determine the most efficient way to
parenthesize a sequence of matrices A[1 … n] so that the total number of scalar
multiplications is minimized.
The fundamental idea is to split the chain of matrices into two parts at some position k,
where:
1≤k<n
This gives two subchains:
[Link] subchain: A[1 … k]
[Link] subchain: A[k+1 … n]
Divide and Conquer Limitation:
A pure divide-and-conquer approach cannot be directly used since the optimal value
of k (where the split occurs) is not known in advance.
Dynamic Programming Approach:
Dynamic programming (DP) is applied because:
o It allows trying all possible values of k.
o It stores subproblem results to avoid recomputation.
  A table M[i, j] is used to store the minimum cost (number of scalar multiplications)
needed to compute A [i... j] .
 The diagonal entries M [i, i]=0 , because a single matrix needs no multiplication.
Matrix Dimensions:
For a chain split at position k:
o A [i... k ]→ dimension = pi−1 × p k

o A [k + 1... j]→ dimension = pk × p j

Cost of multiplying these two parts = pi−1 × p k × p j

Recursive Formula

0 if i= j
M [i, j]={
min ⁡i ≤k< j (M [i, k ]+ M [k +1 , j]+ p i−1 pk p j ) if i< j
This formula checks all possible k, calculates the cost, and picks the minimum.
Complexity Analysis:
Complexity Analysis There are three for-loops in the algorithm, and each loop is executed n

times. Therefore, the complexity of the algorithm

Gaussian Elimination method
Gaussian Elimination is a systematic technique used to solve a system of linear equations.
It transforms the given equations into a simpler form from which the solution of unknown
variables can be easily obtained.
A simple linear equation is of the form:
Ax= y
 If A ≠ 0, then the solution is
y
x=
A
 If A=0and y=0, any value of x satisfies the equation (infinitely many solutions).
 If A=0and y ≠ 0, there is no solution.
Gaussian elimination extends this idea to multiple linear equations with several unknowns.
Finding the inverse of a matrix is a time-consuming task. To simplify the problem, the
Gaussian elimination method is used instead.
This approach aims to transform the given system of equations into a simpler equivalent
form that is easier to solve.
The matrix A is systematically reduced (using elementary row operations) to an upper-
triangular matrix, denoted as A '.
That means all the entries below the leading diagonal become zero, resulting in a structure
like this:

b '=¿]
Algorithm:

Pivot element:
 Take the first element a 11(top-left corner) as the pivot element.
 Use this pivot to make all the numbers below it (in the same column) zero.
For example:
To eliminate a 21(the element below a 11),
replace the second row with:
a21
Row 2=Row 2−( )× Row 1
a11
a21
is called the multiplier.
a11
It tells you how much of the first row needs to be subtracted from the second row to make
a 21=0.

 (a 31/a 11 )to eliminate a 31

 Use (a 41 /a11 )to eliminate a 41, and so on.

Complexity

Time complexity:
Gaussian elimination works by eliminating elements below the pivot in each column.
To find its time complexity, we count the number of operations.
1. First column
Eliminating the first column requires about:
2
(n−1)( n+1)=n −1 operations.
2. Next columns
For the second column, the remaining problem size becomes (n−1) ,
for the third column (n−2), and so on.
The total operations are:
 n

∑ ❑¿
k =1

3. Final result
This summation simplifies to approximately:
3 2
n n n
+ +
3 2 6
The highest-order term is n3 , so the time complexity of Gaussian elimination is:
3
O(n )
LU decomposition :
LU decomposition or factorization of a matrix is the factorization of a given square matrix
into two triangular matrices, one upper triangular matrix and one lower triangular matrix,
such that the product of these two matrices gives the original matrix.
Let us assume that matrix A is decomposed into two matrices L and U.
Then the equation Ax = b
can be rewritten, by substituting
A = LU
LUx = b
First, let us assume that y = Ux,
which yields the following equation: Ly = b and solve for y.
Then solve Ux = y to find the unknowns x of the linear equations.
LUP Decomposition
LUP decomposition is an extension of LU decomposition that incorporates pivoting.
During Gaussian elimination, each step uses a pivot element to eliminate entries below it. If
that pivot is:
 Zero → elimination cannot continue
 Very small → round-off errors become large → leads to unstable results
To overcome this, we swap rows so the largest possible pivot is selected. This improves
numerical accuracy and avoids division issues.

Instead of performing these row swaps repeatedly and explicitly, the LUP decomposition
method uses a permutation matrix to record the row interchanges.
In LUP decomposition, a given matrix A is decomposed into three matrices:
PA=LU
Where:
 Lis a lower-triangular matrix
 U is an upper-triangular matrix
 Pis a permutation matrix that captures the row swaps performed during the
elimination process

Solving a System Using LUP

For a system of linear equations:
Ax=b
Multiply both sides by P:
PAx=Pb
Since PA=LU , we rewrite it as:
LUx=Pb
We now solve this in two steps:
1. Forward Substitution
Let y=Ux .
First, solve the equation:
Ly=Pb
Since Lis lower-triangular, this step is efficient.
 2. Back Substitution
Next, solve:
Ux= y
Since U is upper-triangular, this step gives the solution vector x .
Example:
1. LUP decomposition (record swaps & multipliers)
 Swap rows 0↔1 (because pivot A00=0). New matrix:
2 1 4
1
[ 0 3 1 ].Multipliers for column 1: m 21=0/2=0 , m31=1/2= .
2
1 5 2
After elimination:
2 1 4
0 3 1
[ ].
9
0 0
2
9
 In column 2 choose pivot between rows 1 and 2: is larger than 3so swap rows 1↔2.
2
2 1 4
9
Matrix becomes [ 0 0 ].
2
0 3 1
9 2
Multiplier to eliminate below pivot: m 32=3/( )= .
2 3
After elimination we get upper triangular
2 1 4
9
U =[ 0 0 ].
2
0 0 1
 Permutation matrix (rows permuted to order [1,2,0]):
0 1 0
P=[ 0 0 1 ].
1 0 0
 Lower triangular (multipliers in elimination order):
1 0 0
1
1 0
L=[ 2 ].
2
0 1
3
(You can check PA=LU .)
2. Compute Pb.
0 1 0 1 2
Pb=[ 0 0 1 ][ 2 ]=[ 3 ].
1 0 0 3 1
Set Ly=Pb.

3. Forward substitution Ly=Pb.

Equations:
 y 1=2.
1 1
 y + y =3 ⇒ y 2=3− ⋅2=2.
2 1 2 2
2 2 4 −1
 0 ⋅ y 1 + y 2 + y 3=1 ⇒ y 3=1− ⋅2=1− = .
3 3 3 3
So
2
y=[ 2 ].
−1
3

4. Back substitution Ux= y .

Upper system:
2 x1 +1 x 2+ 4 x 3= y 1=2 ,
9
x +0 ⋅ x 3= y 2=2 ,
2 2
−1
1⋅ x 3= y3 = .
3
Solve bottom-up:
−1
 x 3= .
3
y2 2 4
 x 2= =2 ⋅ = .
9/2 9 9
 2 x1 + x 2 +4 x 3 =2⇒ 2 x 1=2− x2−4 x 3 .
4 −1 4 12 −8
Compute x 2+ 4 x 3= + 4 ⋅( )= − = .
9 3 9 9 9
−8 8 26
Thus 2 x1 =2−( )=2+ = .
9 9 9
13
So x 1= .
9
5. Final solution
x=¿]
Finding Matrix Inverse:
 Finding Matrix Inverse Finding the inverse of a matrix is a classic example of the
transform-and-conquer technique, where the problem of finding a matrix inverse is
transformed into a problem of Gaussian elimination to find the entries of an inverse.
 Transform and Conquer is an algorithm design technique in which a problem is first
transformed into another form that is easier or faster to solve.