Является ли алгоритм Томаса самым быстрым способом решения симметричной диагонально доминирующей разреженной трехдиагональной линейной системы

Мне интересно, является ли алгоритм Томаса самым быстрым (доказуемо?) Решением симметричной диагонально доминирующей разреженной трехдиагональной системы с точки зрения алгоритмической сложности (не ища пакетов реализации, таких как LAPACK и т. Д.). Я знаю, что и алгоритм Томаса, и многосетка имеют сложность , но, возможно, постоянный множитель для многосетки меньше? Мне не кажется, что многосетка может быть быстрее, но я не уверен.$O(n)$

Примечание: я рассматриваю случай, когда матрицы очень большие. Возможны прямые или итерационные методы.

Я считаю, что сравнивать итерационный метод (многосеточный) с прямым / точным методом (Томас) с точки зрения точного количества операций не имеет смысла. IIRC, число операций Томаса для$8N$ любого трехдиагональной системы. Единственное время, которое я могу себе представить, можно предположить, что многосеточное избиение является тривиальным случаем наличия линейного решения, и даже тогда стоимость оценки остатка на каждом уровне будет сопоставима со стоимостью Томаса.

полезность многосеточных заключается в томчто это вообще для разреженных матриц, а не ограничивается трехдиагональные системами.$O(N)$

Короткий ответ: алгоритм Томаса будет быстрее любой итерационной схемы почти во всех случаях. Исключением может быть применение одной итерации очень простой итерационной схемы, такой как Гаусс-Зейдель, но вряд ли это даст приемлемое решение. Кроме того, это игнорирует проблемы параллельной обработки.

$\mathcal O(n)$$\mathcal O(n)$ операций, где n - число неизвестных на этом многосеточном уровне.

$5N$$3N$$3N-2$$2N-2$

Многосеточные циклы даже на одном ядре оптимизируются векторизатором. Таким образом, хотя подсчет операций может помочь, мы не должны забывать, что даже в последовательном мире процессоры имеют векторный параллелизм, и, следовательно, время до решения может быть не совсем тем, что мы предсказываем из анализа затрат.