ИСТИНА

При моделировании многих физических процессов необходимо находить решение систем линейных алгебраических уравнений. Для этого часто применяются итерационные численные методы, важным этапом работы которых является умножение матрицы на вектор. Однако, на современных вычислительных системах операция умножения разреженной матрицы на вектор обладает крайне низкой производительностью ввиду того, что время обмена данными с памятью доминирует над временем вычислений. Одним из способов повышения эффективности операции умножения матрицы на вектор является оптимизация форматов хранения разреженных матриц. В ходе проведенной работы были изучены существующе форматы хранения матриц и исследованы их преимущества и недостатки применительно к интересующему классу задач решения систем линейных алгебраических уравнений. Были предложены две модификации для популярного формата хранения данных Compressed Sparse Row (CSR), направленные на сокращение объема памяти для хранения номеров столбцов ненулевых элементов матрицы. Также разработаны критерий применимости исследуемых форматов и теоретические оценки их эффективности. Новые форматы хранения данных реализованы в библиотеке численных методов XAMG и протестированы на расширенном наборе тестовых задач. Показано, что для операции умножения матрицы на вектор достигается ускорение порядка 1.28 и 1.16 раза при вычислениях с плавающей точкой одинарной и двойной точности. Непосредственно при решении систем уравнений достигаемое ускорение составляет порядка 15% и 10% для одинарной и двойной точности соответственно.