разреженная матрица переопределенной системы линейных уравнений библиотека c/c++

Мне нужна библиотека для решения систем Ax=b, где A — несимметричная разреженная матрица с 8 элементами в строке (и она может быть довольно большой). Я думаю, что библиотека, реализующая бисопряженный градиент, должна подойти, но я не могу найти работающую (я пробовал iml++, но в пакетах iml++/sparselib++ отсутствуют некоторые заголовки). Какие-нибудь советы?


c++ sparse-matrix algebra equation
person tuccio    schedule 29.10.2011    source источник
comment
Вы смотрели на boost.org/doc/ libs/1_47_0/libs/numeric/ublas/doc/index.htm?   -  person andand    schedule 29.10.2011
comment
да, но я думаю, что ublas - это просто библиотека шаблонов, я не вижу никакого итеративного метода для решения разреженных систем, я ошибаюсь?   -  person tuccio    schedule 29.10.2011
comment
Существует класс разреженных матриц. Я не очень подробно рассматривал, есть ли для него решатель, но вы можете посмотреть на boost.org/doc/libs/1_47_0/libs/numeric/ublas/doc/, чтобы узнать, есть ли там что-то, что вы можете использовать.   -  person andand    schedule 29.10.2011
comment
да, я уже прочитал эту страницу, но я сомневаюсь, что есть какой-либо решатель   -  person tuccio    schedule 29.10.2011

Ответы (3)


arrow_upward
3
arrow_downward

Существуют стандартные способы обработки переопределенных систем. Например, Википедия говорит следующее:

Система линейных одновременных уравнений может быть записана в матричной форме как Ax = y. Если уравнений больше, чем переменных, система называется переопределенной и не имеет (в общем случае) решений. Затем систему можно изменить на (ATA)x = ATy. Новая система имеет столько же уравнений, сколько и переменных (матрица ATA — квадратная матрица) и решается обычным образом. Решение представляет собой решение методом наименьших квадратов исходной переопределенной системы, сводящее к минимуму евклидову норму ||Ax − y||, меру расхождения между двумя сторонами в исходной системе.

Поэтому вы можете использовать любой стандартный решатель разреженных квадратных матриц.

Лично я использую прямой решатель от CSparse Тима Дэвиса. Тим написал ряд отличных прямых разреженных решателей. Действительно, его UMFPACK является еще одним отличным вариантом и используется, например, в MATLAB. . Обратите внимание, что оба этих решателя предлагают интерфейсы C. Если вы ищете что-то с родным интерфейсом C++, то мне нечего предложить.

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

person David Heffernan    schedule 29.10.2011
comment
большое спасибо, это было полезно, я использую umfpack прямо сейчас (было довольно неприятно делать проект визуальной студии для его компиляции: D), кажется, он работает нормально - person tuccio; 30.10.2011
comment
но еще один вопрос .. учитывая A, как я могу решить A ^ tAx = A ^ tb с помощью umfpack? я имею в виду, дает ли umfpack способ вычислить A^tA и A^tb или мне нужно умножать самостоятельно? (с A ^ t, я имею в виду транспонированный A) - person tuccio; 30.10.2011
comment
Я не знаком с подпрограммами UMFPACK. Как я уже сказал, я использую CSparse, потому что, как это ни парадоксально, простейшие алгоритмы лучше всего подходят для решения моих задач. Но я считаю, что вам нужно сформировать A^tA и A^tb самостоятельно. Конечно, у CSparse есть подпрограммы для создания этих продуктов. Я бы ожидал, что UMFPACK сделает то же самое. - person David Heffernan; 31.10.2011
comment
теперь я использую eigen (eigen.tuxfamily.org/index.php?title=Main_Page) привязки для umfpack, которые реализуют некоторые операции с разреженными матрицами, которые мне нужны, и позволяют мне вызывать функции umfpack с чистым интерфейсом, спасибо за помощь - person tuccio; 31.10.2011

arrow_upward
0
arrow_downward

Похоже, что ARPACK решает проблемы с разреженными несимметричными матрицами. Есть версия на С++.

person Eric LaForce    schedule 29.10.2011
comment
ARPACK — это собственный решатель. При этом великолепно, но вопрос касается другой проблемы. - person David Heffernan; 29.10.2011

arrow_upward
0
arrow_downward

К ответу Дэвида Хеффернана: не забывайте одну важную вещь: необходимо проверить/доказать, что матрица A имеет линейно независимые столбцы, иначе может случиться так, что (A ^ T A) является сингулярным (и тогда это, конечно, не сработает).

person fakub    schedule 03.02.2014