Самый эффективный способ решения системы линейных уравнений

Question

У меня есть (n x n) симметричная матрица A и вектор (n x 1) B. В принципе, мне просто нужно решить Ax = b для x. Проблема в том, что A будет потенциально массовым. Поэтому я ищу наиболее эффективный алгоритм решения линейных уравнений в C++. Я просмотрел библиотеку Эйгена. По-видимому, у него есть метод SVD, но мне сказали, что он медленный. Решение x = обратное (A) * b также похоже на субоптимальное. UBLAS быстрее? Есть ли более эффективные методы? Благодарю.

Редактировать: матрица A положительно определена и не разрежена.

Answer 1

Лучший способ решить Система линейных уравнений формы Ax = b - это сделать следующее.

• разобранное A в формат A = M1 * M2 (где M1 и M2 треугольные)
• Решить M1 * y = b для y с помощью обратной подстановки
• Решить M2 * x = y для x с помощью обратной подстановки

Для квадратных матриц, шаг 1 будет использовать LU Decomposition ,

Для не квадратные матрицы, шаг 1 будет использовать QR Decomposition.

Если матрица А является положительно определенной и не разреженной, вы должны использовать Cholesky Decomposition для первого шага.

Если вы хотите использовать eigen, вам нужно будет сначала decompose it, а затем triangular solve.

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

• LAPACK Netlib в: Documentation и Download (бесплатно)
• MKL от Intel: Documentation и Download (Бесплатно для некоммерческого использования).
• ACML от AMD: Download (бесплатно)
• PLASMA: Download (свободный, многоядерный оптимизированный)
• МАГМА: Download (бесплатно, Реализовано в CUDA, OpenCL)
• CULA: Download (Freemium, Реализовано в CUDA).

Если вы используете eigen в общем проекте, вы можете связать процедуру LAPACK, как вам нужно, как описано here.