O'Reilly logo

Numerical Linear Algebra with Applications by William Ford

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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=[a1b1000b1a2b2000b2a3b3000b3a4b4000b4a5].

si163_e

Write A as a sum of two matrices as follows:

T=[a1b1000b1a2b200000a3b2b3000b3a4b4000b4a5]+[000000b2b2000b2b2000000000000].

If we let

T1=

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required