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:
“The true reformer does not want time, nor money, nor coöperation, nor advice. What is time but the stuff delay is made of? And depend upon it, our virtue will not live on the interest of our money. He expects no income, but outgoes; so soon as we begin to count the cost, the cost begins. And as for advice, the information floating in the atmosphere of society is as evanescent and unserviceable to him as gossamer for clubs of Hercules.”
—Henry David Thoreau (1817–1862)
“To call a posit a posit is not to patronize it. A posit can be unavoidable except at the cost of other no less artificial expedients. Everything to which we concede existence is a posit from the standpoint of a description of the theory-building process, and simultaneously real from the standpoint of the theory that is being built.”
—Willard Van Orman Quine (b. 1908)
“It breedeth no small offence and scandal to see and consider upon the one part the curiosity and cost bestowed by all sorts of men upon their private houses; and on the other part the unclean and negligent order and spare keeping of the houses of prayer by permitting open decays and ruins of coverings of walls and windows, and by appointing unmeet and unseemly tables with foul cloths for the communion of the sacrament.”
—Elizabeth I (1533–1603)