Cost
Each Jacobi rotation can be done in n steps when the pivot element p is known. However the search for p requires inspection of all N ≈ ½ n2 off-diag elements. We can reduce this to n steps too if we introduce an additional index array with the property that is the index of the largest element in row i, (i = 1, …, n − 1) of the current S. Then (k, l) must be one of the pairs . Since only columns k and l change, only must be updated, which again can be done in n steps. Thus each rotation has O(n) cost and one sweep has O(n3) cost which is equivalent to one matrix multiplication. Additionally the must be initialized before the process starts, this can be done in n2 steps.
Typically the Jacobi method converges within numerical precision after a small number of sweeps. Note that multiple eigenvalues reduce the number of iterations since .
Read more about this topic: Jacobi Eigenvalue Algorithm
Famous quotes containing the word cost:
“If music in general is an imitation of history, opera in particular is an imitation of human willfulness; it is rooted in the fact that we not only have feelings but insist upon having them at whatever cost to ourselves.... The quality common to all the great operatic roles, e.g., Don Giovanni, Norma, Lucia, Tristan, Isolde, Brünnhilde, is that each of them is a passionate and willful state of being. In real life they would all be bores, even Don Giovanni.”
—W.H. (Wystan Hugh)
“Apparently, a democracy is a place where numerous elections are held at great cost without issues and with interchangeable candidates.”
—Gore Vidal (b. 1925)
“This people must cease to hold slaves, and to make war on Mexico, though it cost them their existence as a people.”
—Henry David Thoreau (1817–1862)