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

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=\left[\begin{array}{ccccc}{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{array}\right].$

Write A as a sum of two matrices as follows:

$T=\left[\begin{array}{ccccc}{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{array}\right]+\left[\begin{array}{ccccc}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{array}\right].$

If we let

${T}_{1}=$

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

No credit card required
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 3, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}