Библиотека линейных сопряжённых градиентных методов (LibLCG): описание

Автор: Чжан Ичжан (yizhang-geo@zju.edu.cn)

Университет Земли и космических исследований Чжэцзян, Институт исследования физики Земли

Это описание охватывает только краткое введение в библиотеку алгоритмов и её использование. Для получения более подробной информации рекомендуется обратиться к комментариям в коде. Если у вас есть дополнительные вопросы, пожалуйста, свяжитесь со мной по электронной почте. Также я буду рад видеть заинтересованных студентов в нашей команде разработчиков!

Введение

LibLCG — это эффективная и расширяемая библиотека C++ для линейных сопряжённых градиентных алгоритмов. Она основана на собственных структурах данных и предоставляет интерфейсы на основе Eigen3 и CUDA, что позволяет легко реализовать параллельные вычисления на CPU или GPU.

Библиотека включает в себя различные вещественные и комплексные сопряжённые градиентные алгоритмы, а также другие итерационные методы решения. В настоящее время доступны следующие методы:

— метод сопряжённых градиентов; — предобусловленный метод сопряжённых градиентов; — метод квадратичных сопряжённых градиентов; — двухуровневый метод сопряжённых градиентов; — BB-шаг метода сопряжённых градиентов с проекцией; — SPG-метод сопряжённых градиентов с проекцией.

Для комплексных чисел доступны:

— метод двойных сопряжённых градиентов; — метод сопряжённого градиента; — предобусловленный метод сопряжённого градиента; — TFQMR-метод.

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

Сопряжённые градиентные методы могут быть использованы для решения систем линейных уравнений вида:

Ax = B

где A — квадратная матрица порядка N, x — вектор неизвестных размера Nx1, B — вектор свободных членов размера Nx1. Обратите внимание, что разные типы сопряжённых градиентных методов могут иметь разные требования к матрице A, например, она должна быть положительно определённой или симметричной. Конкретные требования для каждого метода можно найти в других источниках или в комментариях к коду.

Установка

Алгоритмическая библиотека использует CMake для сборки, позволяя создавать соответствующие Makefile или проектные файлы для различных операционных платформ.

Параметры компиляции

В настоящее время доступны следующие параметры компиляции:

• LibLCG_OPENMP: использовать ли OpenMP для ускорения. По умолчанию включено.
• LibLCG_EIGEN: компилировать ли алгоритмы и интерфейсы на основе Eigen. По умолчанию включено.
• LibLCG_STD_COMPLEX: использовать ли std::complex в качестве типа комплексных чисел по умолчанию. По умолчанию включено.
• LibLCG_CUDA: компилировать ли алгоритмы и интерфейсы на базе CUDA. По умолчанию включено.

Пользователи могут настроить параметры компиляции с помощью команды cmake с параметром -D. Например, чтобы отключить LibLCG_Eigen, используйте следующую команду:

cmake -DLibLCG_EIGEN=OFF

Linux и MacOS

По умолчанию библиотека LibLCG устанавливается в каталог /usr/local. Заголовочные файлы и динамические библиотеки находятся в папках include и lib соответственно. Процесс установки и компиляции выглядит следующим образом:

1. Загрузите и установите CMake.
2. Скачайте и установите GCC-компилятор (обычно уже присутствует в системе).
3. В папке с исходными файлами выполните следующие команды для компиляции и установки:

mkdir build && cd build && cmake .. && make install

Windows

MinGW и GCC

Windows не содержит GNU-среду разработки, поэтому её необходимо установить самостоятельно. Вот как это сделать:

1. Скачайте файл установки MinGW, выбрав пакеты gcc, pthreads и make.
2. Установите CMake.
3. Добавьте пути к исполняемым файлам CMake и MinGW в переменные среды Windows.
4. В папке с исходным кодом выполните следующие команды для компиляции и установки:

mkdir build && cd build && cmake .. -G "MinGW Makefiles" && make install

Обратите внимание, что по умолчанию библиотека устанавливается в папку C:/Program Files. Заголовочные файлы и динамические библиотеки располагаются в папках include и lib соответственно.

Примечание: пользователям необходимо вручную добавить пути к заголовочным файлам и динамическим библиотекам в системные переменные.

Visual Studio

Можно использовать CMake для создания проекта Visual Studio и компиляции динамических библиотек. Вот как это делается:

1. Установите Visual Studio.
2. Установите CMake.
3. В исходной папке выполните следующие команды, чтобы создать проект Visual Studio:

mkdir build && cd build && cmake .. -G "Visual Studio 16 2019"

Примечание: для генерации проектов других версий Visual Studio используйте параметр -G для просмотра соответствующих идентификаторов.

4. Откройте проект .sln в Visual Studio и скомпилируйте динамическую библиотеку.

Использование и компиляция

При использовании функций библиотеки в исходном коде необходимо включить соответствующий заголовочный файл, например:

#include "lcg/lcg.h"

Во время компиляции исполняемого файла необходимо связать библиотеку lcg. Используйте g++ в качестве примера:

g++ example.cpp -llcg -o example_out

Быстрый старт

Чтобы использовать LibLCG для решения системы линейных уравнений Ax = B, необходимо определить функцию, которая вычисляет произведение Ax. Эта функция называется «обратный вызов» и имеет следующий интерфейс:

typedef void (*lcg_axfunc_ptr)(void* instance, const lcg_float* x, lcg_float* prod_Ax, const int n_size);

Здесь x — входной вектор, prod_Ax — возвращаемый вектор произведения, n — длина обоих векторов. Обратите внимание, что список параметров не включает матрицу A. Это связано с тем, что в некоторых сложных задачах оптимизации A может не существовать или её хранение и вычисление могут быть нецелесообразными. Вместо этого обычно хранят связанные переменные и вычисляют только произведение Ax.

После определения функции обратного вызова можно вызвать функцию решения lcg_solver() для решения системы уравнений. Рассмотрим пример функции решения без ограничений:

int lcg_solver(lcg_axfunc_ptr Afp, lcg_progress_ptr Pfp, lcg_float* m, const lcg_float* B, const int n_size, 
    const lcg_para* param, void* instance, lcg_solver_enum solver_id = LCG_CGS);

Параметры функции включают:

1. lcg_axfunc_ptr Afp — функция обратного вызова для вычисления Ax;
2. lcg_progress_ptr Pfp — функция обратного вызова для мониторинга процесса итерации (необязательна, можно использовать nullptr, если мониторинг не требуется);
3. lcg_float *m — начальный вектор решения, который также сохраняет результат итераций;
4. const lcg_float *B — член B в уравнении Ax = B;
5. const int n_size — размер вектора решения;
6. const lcg_para *param — параметры итерации, которые можно опустить, используя nullptr для использования значений по умолчанию;
7. void *instance — экземпляр объекта, переданный в функцию (в классе это указатель this, в обычной функции — nullptr);
8. int solver_id — метод решения, используемый функцией lcg_solver (можно посмотреть в соответствующем заголовочном файле).

Пример

Вот простой пример использования библиотеки:

#include <cmath>
#include <iostream>
#include "lcg/lcg.h"

#define M 100
#define N 80

// Возвращает максимальное различие между элементами двух массивов
lcg_float max_diff(const lcg_float *a, const lcg_float *b, int size) {
    lcg_float max = -1;
    for (int i = 0; i < size; i++) {
        max = lcg_max(sqrt((a[i] - b[i])*(a[i] - b[i])), max);
    }
    return max;
}

// Двумерный массив для ядра
lcg_float **kernel;
// Промежуточный результат
lcg_float *tmp_arr;

// Функция обратного вызова для lcg_solver
void CalAx(void* instance, const lcg_float* x, lcg_float* prod_Ax, const int n_s) {
    // Обратите внимание, что ядро фактически представляет собой kernel^T * kernel и имеет размер N*N
    lcg_matvec(kernel, x, tmp_arr, M, n_s, MatNormal); // tmp_tar = kernel * x
    lcg_matvec(kernel, tmp_arr, prod_Ax, M, n_s, MatTranspose); // prod_Ax = kernel^T * tmp_tar
    return;
}

// Определяем функцию обратного вызова для отслеживания прогресса
// Эта функция отображает текущий номер итерации и значение сходимости
int Prog(void* instance, const lcg_float* m, const lcg_float converge, const lcg_para* param, const int n_s, const int k) {
    std::clog <<