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:
“Oh high is the price of parenthood,
And daughters may cost you double.
You dare not forget, as you thought you could,
That youth is a plague and a trouble.”
—Phyllis McGinley (20th century)
“To become a token woman—whether you win the Nobel Prize or merely get tenure at the cost of denying your sisters—is to become something less than a man ... since men are loyal at least to their own world-view, their laws of brotherhood and self-interest.”
—Adrienne Rich (b. 1929)
“The cost of a thing is the amount of what I will call life which is required to be exchanged for it, immediately or in the long run.”
—Henry David Thoreau (1817–1862)