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:
“One must always be aware, to notice—even though the cost of noticing is to become responsible.”
—Thylias Moss, African American poet. As quoted in the Wall Street Journal (May 12, 1994)
“History is strewn with the wrecks of nations which have gained a little progressiveness at the cost of a great deal of hard manliness, and have thus prepared themselves for destruction as soon as the the movements of the world gave a chance for it.”
—Walter Bagehot (1826–1877)
“The Fountaine of parents duties is Love....Great reason there is why this affection should be fast fixed towards their children. For great is that paine, cost, and care, which parents must undergoe for their children. But if love be in them, no paine, paines, cost or care will seeme too much.”
—William Gouge (20th century)