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