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 one regret I have about my own abortions is that they cost money that might otherwise have been spent on something more pleasurable, like taking the kids to movies and theme parks.”
—Barbara Ehrenreich (b. 1941)
“[M]y conception of liberty does not permit an individual citizen or a group of citizens to commit acts of depredation against nature in such a way as to harm their neighbors and especially to harm the future generations of Americans. If many years ago we had had the necessary knowledge, and especially the necessary willingness on the part of the Federal Government, we would have saved a sum, a sum of money which has cost the taxpayers of America two billion dollars.”
—Franklin D. Roosevelt (1882–1945)
“I acknowledge that the balance I have achieved between work and family roles comes at a cost, and every day I must weigh whether I live with that cost happily or guiltily, or whether some other lifestyle entails trade-offs I might accept more readily. It is always my choice: to change what I cannot tolerate, or tolerate what I cannot—or will not—change.”
—Melinda M. Marshall (20th century)