Analysis
As is common for divide and conquer algorithms, we will use the Master theorem to analyze the running time. Remember that above we stated we choose . We can write the recurrence relation:
In the notation of the Master theorem, and thus . Clearly, so we have
Remember that above we pointed out that reducing a Hermitian matrix to tridiagonal form takes flops. This dwarfs the running time of the divide-and-conquer part, and at this point it is not clear what advantage the divide-and-conquer algorithm offers over the QR algorithm (which also takes flops for tridiagonal matrices).
The advantage of divide-and-conquer comes when eigenvectors are needed as well. If this is the case, reduction to tridiagonal form takes, but the second part of the algorithm takes as well. For the QR algorithm with a reasonable target precision, this is, whereas for divide-and-conquer it is . The reason for this improvement is that in divide-and-conquer, the part of the algorithm (multiplying matrices) is separate from the iteration, whereas in QR, this must occur in every iterative step. Adding the flops for the reduction, the total improvement is from to flops.
Practical use of the divide-and-conquer algorithm has shown that in most realistic eigenvalue problems, the algorithm actually does better than this. The reason is that very often the matrices and the vectors tend to be numerically sparse, meaning that they have many entries with values smaller than the floating point precision, allowing for numerical deflation, i.e. breaking the problem into uncoupled subproblems.
Read more about this topic: Divide-and-conquer Eigenvalue Algorithm
Famous quotes containing the word analysis:
“A commodity appears at first sight an extremely obvious, trivial thing. But its analysis brings out that it is a very strange thing, abounding in metaphysical subtleties and theological niceties.”
—Karl Marx (1818–1883)
“... the big courageous acts of life are those one never hears of and only suspects from having been through like experience. It takes real courage to do battle in the unspectacular task. We always listen for the applause of our co-workers. He is courageous who plods on, unlettered and unknown.... In the last analysis it is this courage, developing between man and his limitations, that brings success.”
—Alice Foote MacDougall (1867–1945)
“Analysis as an instrument of enlightenment and civilization is good, in so far as it shatters absurd convictions, acts as a solvent upon natural prejudices, and undermines authority; good, in other words, in that it sets free, refines, humanizes, makes slaves ripe for freedom. But it is bad, very bad, in so far as it stands in the way of action, cannot shape the vital forces, maims life at its roots. Analysis can be a very unappetizing affair, as much so as death.”
—Thomas Mann (1875–1955)