Результаты с direct solver
Evgenii Rudnyi
http://www.cise.ufl.edu/research/sparse/matrices/AMD/G3_circuit.html
На моем ноутбук с 2 Гб памяти, см. первый компьютер в Таблице 1
http://matrixprogramming.com/MatrixMultiply/#Conclusion
получилось:
Факторизация с MUMPS - 62 s
Факторизация с TAUCS - 100 s
Получается, что эта матрица хотя и большой размерности n = 1 585 478, но
число ненулевых элементов у нее не очень большое, и также она хорошо
упорядочивается и в факторе не очень много ненулевых значений.
Я также попробовал свои матрицы
http://www.imtek.uni-freiburg.de/simulation/benchmark/wb/bone/
но с 2 Гб памяти проходит только BS01
Факторизация с MUMPS - 29 s
Факторизация с TAUCS - 32 s
Некоторое время назад на 450 MHz Sun факторизация с TAUCS была 145 s:
http://modelreduction.com/doc/papers/rudnyi05ulm.pdf
Было бы интересно посмотреть на результаты с итеративными решателями.
Evgenii Rudnyi
>
> http://www.imtek.uni-freiburg.de/simulation/benchmark/wb/bone/
>
> но с 2 Гб памяти проходит только BS01
>
> Факторизация с MUMPS - 29 s
> Факторизация с TAUCS - 32 s
>
Я запустил эти матрицы на компьютере с 24 Гб памяти. Получились
следующие результаты для MUMPS с одним процессором
Матрица n nnz время факторизации, c память для фактора, Мб
BS01 127224 3421188 33 493
BS10 914898 28191660 245 3173
B010 986703 36326514 1757 11050
B025 2159661 79292769 4681 26030
Вот. Дальше уже можно только в out-of-core.
Должен отметить что матрицы BS и B сильно отличаются друг от друга
связностью. В серии "B" фактор занимает гораздо больше места. Автор
матриц, Bert van Rietbergen говорил, что в этом есть глубокий внутренний
смысл, так как кости в обоих случаях были разные. К слову сказать, ему
нужно решать матрицы размерность более чем 100 миллионов. Это хорошая
область для итеративных решателей, для прямых там потребуется уже памяти
немеренно, даже в out-of-core.
vitaly333
On 22 май, 18:36, Evgenii Rudnyi <use...@rudnyi.ru> wrote:
> Меня попросили для сравнения запустить прямые решатели с матрицей
>
> http://www.cise.ufl.edu/research/sparse/matrices/AMD/G3_circuit.html
>
> На моем ноутбук с 2 Гб памяти, см. первый компьютер в Таблице 1
>
> http://matrixprogramming.com/MatrixMultiply/#Conclusion
>
> получилось:
>
> Факторизация с MUMPS - 62 s
> Факторизация с TAUCS - 100 s
>
> Получается, что эта матрица хотя и большой размерности n = 1 585 478, но
> число ненулевых элементов у нее не очень большое, и также она хорошо
> упорядочивается и в факторе не очень много ненулевых значений.
>
(Reorder = MMD,eps = 1e-8, droptol = 0.003) :
Конфигурация тестовой платформы:
CPU: AMD Athlon 64x2 2.4 GHz;
Memory: 1.5 GB DDR 400 MHz;
Operation System: Windows XP SP2;
IDE: Eclipse 3.3.2;
Compiler: JDK 6.0
Общее время решения : 264 сек.
Кол - во итераций: 106
Память под U: 191 мег.
Результаты для BS01 c решателем SICH2_PCG (Reorder = RCM,eps = 1e-8,
droptol = 0.005) :
Общее время решения : 75 сек.
Память под U: 60 мег.
Кол - во итераций: 138
Из тестов видно что MUMPS ( в 2-5 раз) быстрее итерационного метода
а TAUCS (в 2-3 раза). Но итерационный метод требует куда - более
меньше памяти (493 мб. против 60 мб.). И это его основное приемущество
над прямыми методами. К тому же MUMPS написан на Фортране, TAUCS на С+
+ а мой итерационный метод на JAVA. Фортрановские и Сишные компиляторы
дают определенное приемущество в скорости выполнения кода это раз.
Два - MUMPS и TAUCS используют многоуровневые высокоэффективные
упорядочения (METIS) а в моем решателе таких к сожалению пока нет.
Возможно, что этот итерационный солвер , с использованием METIS и
переписанный на С++ составит конкуренцию этим двум монстрам:-))
А вообще по хорошему сравнение разных решателей должно выполнятся на
одном и том же компьютере , с одной и той же ОС и собранных одним и
тем же компилятором. Но такой возможности для сравнения
вышерассмотренных решателей пока нет. Возможно, что такая возможность
появиться в будущем....
Задачи BS10,B010,B025 пока не удалось решить с 1.5 GB установленной
памяти. Их получается разместить в памяти но предобуславливатель
получается не очень хорошего качества и CG сходится очень долго (>1000
итераций). Более качественный предобуславливатель требует больше
памяти , которая выходит за 1.3 GB (это максимум что может подмять под
себя JVM для 32 битных систем). Нужно ставить x64 и "мозгов"
побольше :-))). Когда раздобуду побольше памяти протестирую
остальные.
Evgenii Rudnyi
> а TAUCS (в 2-3 раза). Но итерационный метод требует куда - более
> меньше памяти (493 мб. против 60 мб.). И это его основное приемущество
> над прямыми методами.
Это конечно. Соответственно здесь лучше проводить сравнение для
примеров, когда фактор не помещается в памяти. А для совсем
высокоразмерных можно использовать только итеративные решатели.
> К тому же MUMPS написан на Фортране, TAUCS на С+
> + а мой итерационный метод на JAVA. Фортрановские и Сишные компиляторы
> дают определенное приемущество в скорости выполнения кода это раз.
Тоже может быть. Тут на sci.math.num-analysis идет обсуждение
Java ready for number crunching? Options
http://groups.google.com/group/sci.math.num-analysis/browse_frm/thread/e1823529b572ac9c
Может быть вам будет интересно. Правда оно идет несколько в другом
направлении.
> Два - MUMPS и TAUCS используют многоуровневые высокоэффективные
> упорядочения (METIS) а в моем решателе таких к сожалению пока нет.
> Возможно, что этот итерационный солвер , с использованием METIS и
> переписанный на С++ составит конкуренцию этим двум монстрам:-))
Если предобуславливатель связан каким то образом с incomplete Cholesky,
то вполне возможно.
> А вообще по хорошему сравнение разных решателей должно выполнятся на
> одном и том же компьютере , с одной и той же ОС и собранных одним и
> тем же компилятором. Но такой возможности для сравнения
> вышерассмотренных решателей пока нет. Возможно, что такая возможность
> появиться в будущем....
Это конечно. Хотя сравнение разных компиляторов тоже полезно. Вот я
вижу, что VC++ Express Edition компилирует мой код для умножения матриц
так, что он выполняется в три раза медленнее, чем с g++. См.
http://groups.google.com/group/sci.math.num-analysis/browse_frm/thread/0b303788cb8b2e52
Мне надо было по внутренним причинам перейти с g++ на VC++. Мне
поставили Express Edition 2005, поскольку это за бесплатно и я хотел
посмотреть, как он оптимизирует циклы. Однако, есть подозрение, что VC++
Express Edition не включает в себя полной оптимизации для С++.
> Задачи BS10,B010,B025 пока не удалось решить с 1.5 GB установленной
> памяти. Их получается разместить в памяти но предобуславливатель
> получается не очень хорошего качества и CG сходится очень долго (>1000
> итераций). Более качественный предобуславливатель требует больше
> памяти , которая выходит за 1.3 GB (это максимум что может подмять под
> себя JVM для 32 битных систем). Нужно ставить x64 и "мозгов"
> побольше :-))). Когда раздобуду побольше памяти протестирую
> остальные.
Берт (автор матриц) также жаловался на плохую сходимость, но он
использовал вообще диагональные предобуславливатели, если я правильно
помню. Я со своей стороны попробую запустить их в out-of-core c MUMPS.
LG
> Было бы интересно посмотреть на результаты с итеративными решателями.
Вы, наверное знаете, что в ANSYS итерационный метод PCG решает
уравнения раз в 5 быстрее, чем прямой решатель. Еще я встречал
замечание, чир неполное разложение в качестве предобуславливателя
эффективно только для матриц среднего размера.
Это также соответствует и моему опыту.
Леонид
Evgenii Rudnyi
>> Было бы интересно посмотреть на результаты с итеративными решателями.
>
> Добрый день, Евгений.
>
> Вы, наверное знаете, что в ANSYS итерационный метод PCG решает
> уравнения раз в 5 быстрее, чем прямой решатель.
В ANSYS действительно хороший итерационный решатель PCG. Он использует
свой предобуславлеватель, разработанный в ANSYS. Правда я бы сказал, что
он до 5 раз быстрее - это зависит от проблемы. Предобуславлеватель
настроен на проблемы из структурной механики и как часто бывает с
итерационными решателя, шаг влево или вправо рассматривается как побег и
жестко карается. Также для пяти раз уровень заданной ошибки должен быть
явно больше, чем 1е-12.
К сожалению PCG нельзя вызвать напрямую для заданной матрицы. Поэтому
сложно сказать, что будет с матрицами для костей.
> Еще я встречал
> замечание, чир неполное разложение в качестве предобуславливателя
> эффективно только для матриц среднего размера.
> Это также соответствует и моему опыту.
У меня здесь нет никакого опыта, поэтому ничего сказать не могу.
В любом случае мои результаты и матрицы должны быть полезны для
разработчкиов итерационных решателей в качестве точки отсчета.
С другой стороны, если вы могли бы дать модели из ANSYS, можно было бы
выписать матрицы и тогда люди могли бы сравнивать свои разработки также
с PCG.
Евгений
vitaly333
> неполное разложение в качестве предобуславливателя
> эффективно только для матриц среднего размера.
> Это также соответствует и моему опыту.
>
> Леонид
качестве предобуславливателя использовать. Это даже целый класс
предобуславливателей. Их очень много. С различными параметрами....
> Вы, наверное знаете, что в ANSYS итерационный метод PCG решает
> уравнения раз в 5 быстрее, чем прямой решатель.
какого класса?. По моему они вообще закрыли эту информацию...
собственная разработка всё таки.))
Evgenii Rudnyi
...
> Интересто а что там за предобуславливатель? На чем он основан, из
> какого класса?. По моему они вообще закрыли эту информацию...
> собственная разработка всё таки.))
Мне кажется, что эта информация никогда и не была открыта. Эта их
внутренняя разработка.
Вот тут есть недавний любопытный документ
White Paper – Obtaining Optimal Performance in ANSYS 11.0
http://www.tynecomp.co.uk/Xansys/Optimal_Performance_ANSYS_11.pdf
там есть несколько слов.
Я, к слову сказать, попробовал MUMPS out-of-core с матрицами костей. При
этом удалось одолеть B050 где-то за пять часов на одном процессоре. Для
B120 даже в out-of-core 20 Gb памяти уже не хватает.