Комментарии 18
Спасибо,
фундаментальная статья, которую только бегло успел просмотреть. Особое восхищение вызвал образный язык. безусловно улучшающий восприятие. М.б. стоит расширить лит. обзор? Упомянута книга Тима Девиса, но многим нашим читателям известна более старая книга Писсанецки С., Технология разреженных матриц. Там подходы совсем устарели?
фундаментальная статья, которую только бегло успел просмотреть. Особое восхищение вызвал образный язык. безусловно улучшающий восприятие. М.б. стоит расширить лит. обзор? Упомянута книга Тима Девиса, но многим нашим читателям известна более старая книга Писсанецки С., Технология разреженных матриц. Там подходы совсем устарели?
Интересно. Уже 2-я за полгода статья на хабре (более фундаментальная, конечно) о методе решения систем разреженных ЛУ через матрицу связности графов. Первая была от компании 1С.
Но это же разные методы, разве нет?
Я так понял, после очень беглого просмотра, в том посте приведён пример метода BTF (Block-triangular form), при котором общую квадратную матрицу приводят к блочно-треугольному виду и решают отдельно по блокам или типа того. BTF — очень красивая вещь, использующая замкнутые компоненты графа. Надеюсь, напишу о ней когда-нибудь в будущем.
Спасибо за интересную статью! А как вы относитесь к библиотеке Eigen? Быть может есть смысл реализовать в ее рамках такой алгоритм, чтобы он был доступен всем?
Библиотек, посвящённых линейной алгебре, много. Про Eigen слышал то там, то тут, но ни разу не использовал. Как-то не было надобности. Демонстрация на общем языке программирования дана скорее для понимания, что и как происходит, а не для повсеместного использования. Потому что если надо на практике СЛУ решать, тот тут надо использовать уже готовые решатели, расчитанные на реальные задачи, типа UMFPACK (за авторством Девиса, кстати), KLU, MUMPS, SuperLU и т.п. Всё равно до эффективности последних добраться самим будет проблематично (хотя и возможно), да и лишняя трата времени.
Дело в том, что подключить и попробовать разные решатели СЛАУ и понять, какой хорошо подходит для моей задачи, получилось когда я подключил Eigen. Туда можно подключать разные штуки типа решателей от intel (MKL). Я сам плохо разбираюсь в методах решения, поэтому для меня проще подключить и проверить.
Я только хотел поставить лайк статье, но мне на глаза попалось вот это
Вы как хотите, а лично я буду благодарить тех ребят, которые в свое время придумали это для матриц (а может и для графов).
Теперь по делу.
Я правильно понимаю, что вы утверждаете, что если A — разреженная симметричная матрица, то её разложение Холецкого тоже разреженное? Если это так, то где можно об этом почитать? Если честно я всегда считал, что это неверно.
Благодарим бога за формат CSC!
Вы как хотите, а лично я буду благодарить тех ребят, которые в свое время придумали это для матриц (а может и для графов).
Теперь по делу.
А дело в том, что данная процедура прямого хода с разреженной правой частью сама часто используется во внешних циклах и лежит в основе разложения Холецкого и левостороннего (left-looking) LU-разложения.
Но, как уже было сказано ранее, этот аппарат незаменим при факторизациях Холецкого, поэтому помидорами в меня кидаться не стоит.
Я правильно понимаю, что вы утверждаете, что если A — разреженная симметричная матрица, то её разложение Холецкого тоже разреженное? Если это так, то где можно об этом почитать? Если честно я всегда считал, что это неверно.
«Вы как хотите, а лично я буду благодарить тех ребят» Я вот тоже думал написать про ребят, а не бога ))
«если A — разреженная симметричная матрица, то её разложение Холецкого тоже разреженное». Тут ситуация вот в чём. «Разреженна» ли какая-либо матрица или нет — ответить на этот вопрос однозначно без учёта контекста невозможно, потому что это условный термин. Даже матрицу без единого нуля можно представить в формате CSC без проблем, другое дело что это уже будет бессмысленно.
Но! При факторизациях матриц, имеющих большое количество нулей, будь то Холецкий, LU, QR и т.п., почти всегда предполагают, что и матрицы-множители в факторизациях (т.е. L, U) тоже имеют достаточное количество нулей, просто их будет меньше, чем в стартовой матрице. Это предположение взято не из воздуха, а из конкретных соображений, о которых можно было бы упомянуть в отдельном посте, но за примером далеко ходить не надо. Посмотрите в посте алгоритм 3, шаг 2. Отдельная строка в матрице L получается как решение нижнетреугольной системы с разреженной правой частью, что часто даёт разреженное же решение. Но количество ненулей в нём будет больше, чем в правой части, за счёт теоремы Гильберта. Именно так это и работает на практике. Конечно, можно всегда подобрать такую разреженную правую часть для конкретной матрицы, что решение будет сплошь ненулевым, т.е. плотным.
На самом деле, количество дополнительных ненулей, возникающих в факторизациях, — серьёзная проблема. И дело даже не в перегрузе памяти — чёрт с ней, а в дополнительном количестве вычислений с плавающей точкой. Множество этих ненулей называют fill-in. Отдельная большая тема в теории разреженных матриц, называемая fill-reducing orderings, посвящена поиску перестановок строк и столбцов матрицы в рамках символьного анализа таким образом, чтобы по возможности уменьшить fill-in при дальнейших факторизацих. Может как-нибудь напишу об этом отдельно.
Почитать об этом можно в упомянутой мной книге, но подойдёт любая, которая хоть немного затрагивает факторизации разреженных матриц.
«если A — разреженная симметричная матрица, то её разложение Холецкого тоже разреженное». Тут ситуация вот в чём. «Разреженна» ли какая-либо матрица или нет — ответить на этот вопрос однозначно без учёта контекста невозможно, потому что это условный термин. Даже матрицу без единого нуля можно представить в формате CSC без проблем, другое дело что это уже будет бессмысленно.
Но! При факторизациях матриц, имеющих большое количество нулей, будь то Холецкий, LU, QR и т.п., почти всегда предполагают, что и матрицы-множители в факторизациях (т.е. L, U) тоже имеют достаточное количество нулей, просто их будет меньше, чем в стартовой матрице. Это предположение взято не из воздуха, а из конкретных соображений, о которых можно было бы упомянуть в отдельном посте, но за примером далеко ходить не надо. Посмотрите в посте алгоритм 3, шаг 2. Отдельная строка в матрице L получается как решение нижнетреугольной системы с разреженной правой частью, что часто даёт разреженное же решение. Но количество ненулей в нём будет больше, чем в правой части, за счёт теоремы Гильберта. Именно так это и работает на практике. Конечно, можно всегда подобрать такую разреженную правую часть для конкретной матрицы, что решение будет сплошь ненулевым, т.е. плотным.
На самом деле, количество дополнительных ненулей, возникающих в факторизациях, — серьёзная проблема. И дело даже не в перегрузе памяти — чёрт с ней, а в дополнительном количестве вычислений с плавающей точкой. Множество этих ненулей называют fill-in. Отдельная большая тема в теории разреженных матриц, называемая fill-reducing orderings, посвящена поиску перестановок строк и столбцов матрицы в рамках символьного анализа таким образом, чтобы по возможности уменьшить fill-in при дальнейших факторизацих. Может как-нибудь напишу об этом отдельно.
Почитать об этом можно в упомянутой мной книге, но подойдёт любая, которая хоть немного затрагивает факторизации разреженных матриц.
Смею предположить, что автор все-таки имел ввиду неполное разложение.
А есть примеры задач, когда супер-разреженная правая часть ещё и остаётся такой в ходе итераций?
Не совсем понял вопроса. Какие итерации имеются в виду?
Итерации для решения системы с разреженной матрицей, о которых в начале статьи упомянуто.
Всё равно непонятно. Если речь идёт о разложении Холецкого, то поступающие в нижнетреугольный решатель в цикле правые части есть просто столбцы оригинальной матрицы A выше диагонали, а т.к. матрица разреженная, то и столбцы её воспринимаются как таковые тоже. Надеюсь, это отвечает на ваш вопрос.
Но тут надо учитывать факт того, что в разложении Холецкого сама нижнетреугольная матрица постоянно расширяется при добавлении очередной правой части. Это требует, на первый взгляд, постоянной перестройки графа. Но не всё так плохо. Об этом, надеюсь, напишу в следующий раз, т.к. данный пост не о разложении Холецкого как самостоятельной теме.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Использование графов для решения разреженных систем линейных уравнений