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:
“How much would it cost you to stand at the wrong end of a shooting gallery?”
—S.J. Perelman, U.S. screenwriter, Bert Kalmar, Harry Ruby, and Norman Z. McLeod. Groucho Marx, Horsefeathers, Huxley College president to con artist Baravelli (Chico Marx)
“Each is under the most sacred obligation not to squander the material committed to him, not to sap his strength in folly and vice, and to see at the least that he delivers a product worthy the labor and cost which have been expended on him.”
—Anna Julia Cooper (1859–1964)
“I favor the policy of economy, not because I wish to save money, but because I wish to save people. The men and women of this country who toil are the ones who bear the cost of the Government. Every dollar that we carelessly waste means that their life will be so much the more meager. Every dollar that we prudently save means that their life will be so much the more abundant. Economy is idealism in its most practical terms.”
—Calvin Coolidge (1872–1933)