Быстрое, приближенное решение линейных уравнений?

Question

Мне нужно решить систему из N линейных уравнений в качестве промежуточного шага в числовом оптимизаторе. Достаточно простыми алгоритмами AFAIK для этого являются O (N ^ 3) (хотя в какой-то математической статье я видел чрезвычайно сложный алгоритм, который мог бы сделать что-то вроде O (N ^ 2.8) с огромной константой). В некоторых случаях N огромно, то есть несколько тысяч.

Есть ли какой-нибудь хороший способ получить приличное приближенное решение системы линейных уравнений менее чем за O (N ^ 3)?

Редактировать:

Вот еще некоторые подробности, если это вообще поможет.

1. Моя матрица симметрична и не разрежена.

2. Это вторая производная матрица от Ньютона-Рафсона. Я пытаюсь что-то оптимизировать в 2000-мерном пространстве.

Answer 1

Существуют итерационные методы, такие как Якоби, Гаусс-Зайдель, CG, GMRES и т. Д.

Answer 2

Для симметричной матрицы метод сопряженного градиента прост в реализации и превзойдет большинство других итерационных методов (например, Gauss-Seidel, SOR). Основной цикл состоит из умножения матрицы на вектор и нескольких других векторных операций.

После того, как все заработало, вы можете использовать предварительную обработку , чтобы еще больше улучшить сходимость.

Answer 3

Да, если матрица, которую вы получаете из их коэффициентов, является разреженной.Есть метод «Правильное наложение» (на болгарском языке, не уверенный в точном переводе), если у вас есть, например, трехдиагональная матрица, которая работает в O (N).Существуют и другие алгоритмы, которые все еще O (N ^ 3), но достигают невероятных результатов, если матрица соответствует некоторому инварианту, который им требуется (разреженный, преобладающий по диагонали, треугольный и т. Д.).

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

Попробуйте этот поиск.