Есть заведомо несовместная СЛАУ (порядка 10000 переменных и 40000 уравнений), для которой необходимо искать решение в смысле минимизации невязки.
Система сильно разреженная — в каждом уравнении 1 или 2 переменные, а остальные коэффициенты заведомо нулевые.
На этапе разработки модели в matlab для решения этой задачи использовалась функция mldivide, которая отрабатывала менее чем за 0,1с.
При переписывании модели на С++ с использованием Intel MKL данный участок кода стал выполняться ~10-50 секунд в зависимости от того, как я его реализовывал.
Если через прямое использование QR решателя (LAPACKE_dgels) на плотной матрице размером 10к*40к элементов, то получалось секунд 50 и очень много памяти на хранение всей матрицы (много больше, чем потреблял matlab).
Если через преобразование к виду (A^{T}A)x=(A^{T}b) и поиск решения этой совместной системы (с плотной квадратной матрицей 10к*10к) с помощью mkl_dcsrmv, mkl_dcsrmultd для преобразования и LAPACKE_dgesv непосредственно для решения мне удалось получить время порядка 10 секунд на решение.
Получается, что разница во времени с matlab — минимум 2 порядка, что как-то слишком много. Более того, matlab вообще запускался в виртуальной машине на 4-хлетнем ноутбучном CPU, а Intel MKL на новых серверных Xeon E5 v4.
Подскажите, пожалуйста, что я могу делать не так?
Может быть есть реализованные методы быстрого решения именно таких сильно разреженных несовместных СЛАУ о которых я не знаю и о которых не сказано в описании функции mldivide (где вообще говорится, что для моего случая используется QR решатель)?
Здравствуйте, phprus, Вы писали:
P>Подскажите, пожалуйста, что я могу делать не так?
Профилировать надо.
Довольно частые ошибки -- данные храняться тоже спарсево или на каждый чих куча когда из абстрактных слоев вызывается
P>Может быть есть реализованные методы быстрого решения именно таких сильно разреженных несовместных СЛАУ о которых я не знаю и о которых не сказано в описании функции mldivide (где вообще говорится, что для моего случая используется QR решатель)?
SSOR у коллег хорошо себя зарекомендовал. Но зависит от матрицы, насколько хорошо обсуловлена итд.
<Подпись удалена модератором>
Re[2]: Эффективное решение большой несовместной СЛАУ
P>>Подскажите, пожалуйста, что я могу делать не так? D>Профилировать надо. D>Довольно частые ошибки -- данные храняться тоже спарсево или на каждый чих куча когда из абстрактных слоев вызывается
Все время тратится внутри MKL (даже внутри одной функции — LAPACKE_dgels или LAPACKE_dgesv в зависимости от варианта). Доля моего кода в общем времени ничтожна.
Плотные матрицы в API MKL — это просто блок непрерывной памяти. Какие-либо абстракции тут невозможны даже теоретически.
С другой стороны matlab однозначно использует разреженное хранение ибо ему на всю задачу хватает меньше гигабайта памяти, а для хранения плотной матрицы 10к*40к в double потребуется более 3 Гб.
P>>Может быть есть реализованные методы быстрого решения именно таких сильно разреженных несовместных СЛАУ о которых я не знаю и о которых не сказано в описании функции mldivide (где вообще говорится, что для моего случая используется QR решатель)? D>SSOR у коллег хорошо себя зарекомендовал. Но зависит от матрицы, насколько хорошо обсуловлена итд.
Не могу понять, а как это поможет для задачи, где СЛАУ заведомо не совместна?
Все что я знаю об исходной системе я описал в первом сообщении. Других сведений у меня нет. Она строится в зависимости от внешних данных.
Re[3]: Эффективное решение большой несовместной СЛАУ
Здравствуйте, phprus, Вы писали:
P>Здравствуйте, denisko, Вы писали:
P>>>Подскажите, пожалуйста, что я могу делать не так? D>>Профилировать надо. D>>Довольно частые ошибки -- данные храняться тоже спарсево или на каждый чих куча когда из абстрактных слоев вызывается P>Все время тратится внутри MKL (даже внутри одной функции — LAPACKE_dgels или LAPACKE_dgesv в зависимости от варианта). Доля моего кода в общем времени ничтожна. P>Плотные матрицы в API MKL — это просто блок непрерывной памяти. Какие-либо абстракции тут невозможны даже теоретически. P>С другой стороны matlab однозначно использует разреженное хранение ибо ему на всю задачу хватает меньше гигабайта памяти, а для хранения плотной матрицы 10к*40к в double потребуется более 3 Гб.
Т.е. ты пытаешься разреженную матрицу преобразовать в плотную и потом решать методами для плотных? Ну тогда это совсем плохой путь. Попробуй из eigenа хотябы решатели.
P>>>Может быть есть реализованные методы быстрого решения именно таких сильно разреженных несовместных СЛАУ о которых я не знаю и о которых не сказано в описании функции mldivide (где вообще говорится, что для моего случая используется QR решатель)? D>>SSOR у коллег хорошо себя зарекомендовал. Но зависит от матрицы, насколько хорошо обсуловлена итд. P>Не могу понять, а как это поможет для задачи, где СЛАУ заведомо не совместна?
Исходная несовместна, когда ты ее записываешь в виде задачи МНК и, если система уравнений на производные при этом остается разреженной то SSOR вполне себе выход. Если применишь напрямую с исходной матрице, то он просто не сойдется.
Здравствуйте, phprus, Вы писали:
P>Есть заведомо несовместная СЛАУ (порядка 10000 переменных и 40000 уравнений), для которой необходимо искать решение в смысле минимизации невязки. P>Система сильно разреженная — в каждом уравнении 1 или 2 переменные, а остальные коэффициенты заведомо нулевые...
P>>>>Подскажите, пожалуйста, что я могу делать не так? D>>>Профилировать надо. D>>>Довольно частые ошибки -- данные храняться тоже спарсево или на каждый чих куча когда из абстрактных слоев вызывается P>>Все время тратится внутри MKL (даже внутри одной функции — LAPACKE_dgels или LAPACKE_dgesv в зависимости от варианта). Доля моего кода в общем времени ничтожна. P>>Плотные матрицы в API MKL — это просто блок непрерывной памяти. Какие-либо абстракции тут невозможны даже теоретически. P>>С другой стороны matlab однозначно использует разреженное хранение ибо ему на всю задачу хватает меньше гигабайта памяти, а для хранения плотной матрицы 10к*40к в double потребуется более 3 Гб. D>Т.е. ты пытаешься разреженную матрицу преобразовать в плотную и потом решать методами для плотных? Ну тогда это совсем плохой путь. Попробуй из eigenа хотябы решатели.
Попробовал разреженный решатель из eigen (Eigen::SparseQR). На маленьких задачах (порядка 1000 переменных) он раза в 2-3 медленнее, чем применение методов для плотных матриц из Intel MKL.
На тесте матрицы реальных размеров (переменных: 9868, уравнений: 39472) eigen получился медленнее примерно в 20 раз.
Re[2]: Эффективное решение большой несовместной СЛАУ
Здравствуйте, andyp, Вы писали:
A>Здравствуйте, phprus, Вы писали:
P>>Есть заведомо несовместная СЛАУ (порядка 10000 переменных и 40000 уравнений), для которой необходимо искать решение в смысле минимизации невязки. P>>Система сильно разреженная — в каждом уравнении 1 или 2 переменные, а остальные коэффициенты заведомо нулевые...
A>Можно алгоритмы и реализации отсюда попробовать A>http://faculty.cse.tamu.edu/davis/suitesparse.html
Спасибо за ссылку, я читал про эту библиотеку, но там, к сожалению, лицензия GPL, которая мне не подходит.
Может быть существуют хорошие аналоги под LGPL или, что предпочтительнее, BSD, Apache, MPL, etc?
Re[3]: Эффективное решение большой несовместной СЛАУ
Здравствуйте, phprus, Вы писали:
P>Спасибо за ссылку, я читал про эту библиотеку, но там, к сожалению, лицензия GPL, которая мне не подходит. P>Может быть существуют хорошие аналоги под LGPL или, что предпочтительнее, BSD, Apache, MPL, etc?
Честно говоря, не знаю . Автор этой либы вроде бы как раз в матлабе sparse QR и делал. У него книжка по решению разреженных систем есть и статьи по теме. Там перечислена гора софта, использующая его солверы, а в license.txt написано, что с ним можно связаться, чтобы (видимо???) подкупить нужную лицензию.
Re[3]: Эффективное решение большой несовместной СЛАУ
Здравствуйте, andyp, Вы писали:
A>Здравствуйте, phprus, Вы писали:
P>>Спасибо за ссылку, я читал про эту библиотеку, но там, к сожалению, лицензия GPL, которая мне не подходит. P>>Может быть существуют хорошие аналоги под LGPL или, что предпочтительнее, BSD, Apache, MPL, etc?
A>Честно говоря, не знаю . Автор этой либы вроде бы как раз в матлабе sparse QR и делал. У него книжка по решению разреженных систем есть и статьи по теме. Там перечислена гора софта, использующая его солверы, а в license.txt написано, что с ним можно связаться, чтобы (видимо???) подкупить нужную лицензию.
Да? Тогда надо будет протестировать и сравнить скорость работы.
Скорее всего для этого. И я даже могу предположить, сколько нулей будет в возможном счете
Re[5]: Эффективное решение большой несовместной СЛАУ
Здравствуйте, phprus, Вы писали:
P>Да? Тогда надо будет протестировать и сравнить скорость работы. P>Скорее всего для этого. И я даже могу предположить, сколько нулей будет в возможном счете
Зависит от приложения Препода, как правило, достаточно разумны. Если Вы сможете убедить его, что с помощью его либы Вы варите похлебку для бездомных , то счет вряд ли будет слишком велик — что-то всегда лучше чем ничего.
Здравствуйте, phprus, Вы писали:
P>Доброго времени суток!
P>Есть заведомо несовместная СЛАУ (порядка 10000 переменных и 40000 уравнений), для которой необходимо искать решение в смысле минимизации невязки. P>Система сильно разреженная — в каждом уравнении 1 или 2 переменные, а остальные коэффициенты заведомо нулевые.
P>На этапе разработки модели в matlab для решения этой задачи использовалась функция mldivide, которая отрабатывала менее чем за 0,1с.
Матлаб вроде бы сам может сгенерировать C\C++ код?
Кодом людям нужно помогать!
Re[2]: Эффективное решение большой несовместной СЛАУ
Есть вот такая SuperLU библиотека.
Они идет в 3-х вариантах LU, LU_MT и LU_DST
Сам на нее облизываюсь, но никак руки не дойдут. Меня больше интересует SuperLU_DST так как только она умеет задействовать GPU.
Если разберетесь, с ней отпишитесь сюда, как она Вам.
. Автор этой либы вроде бы как раз в матлабе sparse QR и делал. У него книжка по решению разреженных систем есть и статьи по теме. Там перечислена гора софта, использующая его солверы, а в license.txt написано, что с ним можно связаться, чтобы (видимо???) подкупить нужную лицензию.
, то счет вряд ли будет слишком велик — что-то всегда лучше чем ничего.
