Алгоритм Ланцоша для точной арифметики (без переортогонализации)
| Алгоритм Ланцоша для точной арифметики (без переортогонализации) | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]\displaystyle{ O(n^2) + O(k^3) }[/math] |
| - на одну итерацию и O(kn^2) - суммарно для k итераций | |
| Объём входных данных | [math]\displaystyle{ n^2 + n + 1 }[/math] |
| , при экономии памяти затраты сокращаются до \frac{n(n - 1)}{2} + n + 1 | |
| Объём выходных данных | [math]\displaystyle{ k }[/math] |
| , а если нужны собственные векторы, то k + kn | |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | [math]\displaystyle{ O(n) }[/math] |
| Ширина ярусно-параллельной формы | [math]\displaystyle{ O(n^2) }[/math] |