MATLAB линейных наименьших квадратов с разреженным b

Question

Я пытаюсь решить проблему llsq вида Ax = b.У меня есть несколько огромных матриц, где

size(A) = 26181 13090
size(b) = 26181 1

b имеет разреженность ~ 26%, а A почти плотная.Из документов mldivide кажется, что A\b запускает специальный алгоритм, если b редко.

Однако в настоящее время решение занимает более 30 минут (после этого я вручную завершилвремя, поэтому я не знаю, сколько времени на самом деле это займет).

Ищет предложения о том, как ускорить это вычисление.

Answer 1

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

1. Sparsicity: Если вы объявили свою матрицу A или вектор b разреженной, отмените ее.Исчисление в разреженных системах медленнее, чем плотное исчисление для матриц с процентом ненулевых записей, превышающим ~ 20% (не цитируйте меня здесь, только приблизительно).Это относится не только к решению, но и к умножению и всем остальным. Ссылка на разреженные вопросы, SO

2. Оператор обратной косой черты Оператор обратной косой черты анализирует матрицу перед ее решением.В зависимости от атрибутов, он использует другой решатель (LU, Cholesky, ...).Таким образом, это почти всегда самое быстрое и удобное решение.Когда матрица разрежена, оператор обратной косой черты запускает другую процедуру, сначала проверяя различные свойства.Проверьте схемы, представленные в документации Matlab для оператора с обратной косой чертой (внизу) .

Единственный способ решить большую проблему быстрее, чем оператор с обратной косой чертой, - это использоватьитерационный решатель.Эти решатели (например, CG - метод сопряженных градиентов) требуют вычислительных усилий, которые линейно зависят от квадратного корня от размера матрицы.Они чрезвычайно эффективны в больших матричных системах, но медленнее в маленьких.Они также не дают точного решения, но остатки могут быть установлены очень низкими, что дает почти правильное решение.Недостатки большинства итерационных решателей заключаются в том, что они требуют, чтобы ваша матрица удовлетворяла определенным критериям.В случае CG ваша матрица должна быть положительно определенной и симметричной (как пример).Боюсь, что в вашем случае, вероятно, не один из этих итерационных решателей поможет: /

Я надеюсь, что смогу немного прояснить это и пожелать вам удачи!