Решение разреженной матрицы с использованием собственного

Question

Я пишу систему частиц на основе ограничений на основе бумаги this. Якобиан ограничений C масштабируется с числом частиц в системе и количеством ограничений. Поскольку каждое ограничение обычно имеет только несколько частиц, которые зависят от него, матрица будет чрезвычайно разреженной. Я думал, что было бы полезно использовать разреженную матрицу в Эйгене для решения системы. В соответствии с Eigen reference material существует несколько различных методов решения этих разреженных матричных уравнений. Мои вопросы:

1. Возможно, размер этих матриц потребует использования разреженной матрицы? Мне нужно сохранить якобиан и его производную по времени. Каждая из них является матрицей Mx3N, где M - число ограничений, а N - число частиц. Пользователь моей системы частиц может предположительно добавить столько частиц, сколько они хотят по разумным причинам.
2. Является ли аргумент для разреженных матричных представлений более плотной матрицей в большей степени об эффективности или потреблении памяти. Может ли разрешенная матрица быть решена быстрее, чем плотная матрица, и от чего это зависит?
3. Я не очень много знаю об этих реализациях решателя. Я не очень изучал эти алгоритмы, особенно в контексте разреженных матричных уравнений. Какова производительность этих алгоритмов, и какой из них я должен выбрать? Я помню, как несколько лет назад узнал о некоторых из них в классе линейных алгебр, и я считаю, что многие из них были O (n^3), что, похоже, не очень хорошо подходит для такой системы, как описанная в этой статье.

Answer 1

Лучший выбор разреженного линейного решателя зависит от множества факторов, например: (a) насколько велика ваша система (миллионы уравнений не представляют собой нечто необычное); (б) имеет ли он какие-либо конкретные свойства, такие как высокая степень разреженности; (c) является матрицей, плохо обусловленной или хорошо обусловленной, (d) является матрицей, симметричной или нет, (e) является положительно определенной или нет и т. д. Просто для обзора темы, я предлагаю вам посетить на следующей веб-странице (в ней содержатся некоторые идеи и пример, который может оказаться полезным для ваших целей): http://members.ozemail.com.au/~comecau/CMA_Sparse.htm

Answer 2

Если N меньше, чем, скажем, 1000, то вы можете пойти с плотным хранилищем, иначе лучше использовать разреженное представление. Количество не-нулей в строке должно быть очень маленьким, скажем, около 10 и не более 100, чтобы сохранить эффективность решателей. Сложность разреженных решателей на практике меньше, чем O (N * K), где K - число ненулевых значений. Поэтому они могут быть на несколько порядков быстрее, чем плотные решатели для очень разреженных матриц.