Numerical Linear Algebra with Applications

19.6 The Divide-And-Conquer Method

This presentation is a summary of the divide-and-conquer method. For more in-depth coverage of this algorithm, see Refs. [1, pp. 216-228], [19, pp. 359-363], and [26, pp. 229-232].

The recursive algorithm divides a symmetric tridiagonal matrix into submatrices and then applies the same algorithm to the submatrices. We will illustrate the method of splitting the problem into smaller submatrix problems using a 5 ×5 matrix

$T = [\begin{matrix} a_{1} & b_{1} & 0 & 0 & 0 \\ b_{1} & a_{2} & b_{2} & 0 & 0 \\ 0 & b_{2} & a_{3} & b_{3} & 0 \\ 0 & 0 & b_{3} & a_{4} & b_{4} \\ 0 & 0 & 0 & b_{4} & a_{5} \end{matrix}] .$

si163_e

Write A as a sum of two matrices as follows:

$T = [\begin{matrix} a_{1} & b_{1} & 0 & 0 & 0 \\ b_{1} & a_{2} - b_{2} & 0 & 0 & 0 \\ 0 & 0 & a_{3} - b_{2} & b_{3} & 0 \\ 0 & 0 & b_{3} & a_{4} & b_{4} \\ 0 & 0 & 0 & b_{4} & a_{5} \end{matrix}] + [\begin{matrix} 0 & 0 & 0 & 0 & 0 \\ 0 & b_{2} & b_{2} & 0 & 0 \\ 0 & b_{2} & b_{2} & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{matrix}] .$

If we let

$T_{1} =$

Get Numerical Linear Algebra with Applications now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Numerical Linear Algebra with Applications by William Ford

19.6 The Divide-And-Conquer Method

Don’t leave empty-handed

It’s yours, free.

Check it out now on O’Reilly