USPARS — ДЛЯ РЕШЕНИЯ БОЛЬШИХ РАЗРЕЖЕННЫХ СЛАУ

Это мультиплатформенный прямой решатель больших разреженных систем линейных уравнений на многопроцессорных системах с общей памятью.

Разреженные системы уравнений – это системы с матрицами коэффициентов, у которых число ненулевых элементов много меньше размера матрицы. В зависимости от размера доступной памяти, размерности матриц решаемых систем могут достигать несколько миллионов, с несколькими сотнями миллионов ненулевых элементов. В настоящее время доступны реализации решателя USPARS на платформах х86, Эльбрус и АРМ (Apple).

Для повышения производительности вычисления распараллеливаются с использованием библиотеки OpenMP для соответствующей платформы, а для выполнения матричных операций библиотеки BLAS2 и BLAS3 используются оптимизированные библиотеки для данной платформы (например, MKL на х86, eml на Эльбрусе, Accelerator на Apple).

Для хранения разреженных матриц существуют специальные структуры, которые позволяют минимизировать объем требуемой памяти для таких матриц и обеспечить эффективную работу с ними. USPARS использует для хранения и обработки разреженных матриц формат CSR (compressed sparse row). В USPARS входные матрицы для вычислений должны подаваться в таком формате, а в качестве результата выдается плотный вектор решений.

Для решения системы линейных уравнений

A X = F

с разреженной матрицей коэффициентов A размера NxN и плотной матрицей F размера Nxk выполняется разложение матрицы A в произведение нескольких матриц, являющихся нижне- или верхнетреугольными и диагональными, с последующим решением полученных систем уравнений с треугольными матрицами. В USPARS используются несколько видов треугольной факторизации разреженных матриц, конкретный вид определяется принадлежностью матрицы тому или иному классу и задается в виде параметра решателю. В зависимости от свойств симметрии и положительной определенности матрицы коэффициентов используются следующие виды факторизации

USPARS позволяет решать системы с одинарной и двойной точностью. Для хранения матриц, заданных с двойной точностью, требуется в два раза больше памяти, а для вычислений может потребоваться в два раза больше времени. Но использование двойной точности позволяет более точно выполнять арифметические операции, что может быть существенно для матриц с большими числами обусловленности. Для матриц, представленных с одинарной точностью, существует большая вероятность получения недостаточной точности при вычислениях, поэтому рекомендуется по возможности всегда использовать двойную точность.

Наиболее известными аналогами решателя USPARS являются пакеты MKL PARDISO, MUMPS, PARDISO, SuperLU, TAUCS, UMFPACK.

В таблицах и на графиках можно посмотреть сравнительные данные о производительности  решателя USPARS на ряде тестов из специализированной сюиты SuiteSparse Matrix Collection.

Пакет USPARS имеет подробное руководство пользователя. Недавно выпущена первая рабочая версия пакета USPARS 1.0.5.

Достижения команды УНИПРО в разработке программного пакета USPARS освещались в докладах на международных симпозиумах (см. ниже). Можно посмотреть презентации за 2022 и за 2021 гг. В ноябре 2022 г  новые результаты были представлены  на семинаре ИВМиМГ СО РАН.

Если вас интересует информация об этой разработке, напишите нам.

Публикации:

1. M. Cherepanov, V.Kostin, A.Semenov, S.Solovyev. Developing a direct sparse solver for the Elbrus processors. // Тезисы международной конференции “Марчуковские научные чтения-2021”, c.121, Новосибирск, 2021.

2. M. Cherepanov, V.Kostin, A.Semenov, S.Solovyev. Efficient direct sparse solver for different processor architectures. //Тезисы  международной конференции «Марчуковские научные чтения-2022», с.99, Новосибирск, 2022.