Эффективный алгоритм поиска численных решений уравнений эллиптического типа в QTT-форматес использованием z-kron

Данная работа описывает способ решения дифференциального уравнения эллиптического типа с использованием тензорного разложение Quantized Tensor Train (QTT) в качестве структуры для хранения данных. QTT позволяет хранить разреженные матрицы в компактном представлении в памяти ЭВМ. Преимуществом данного тензорного разложения является наличие эффективных реализаций базовых математических операций, таких как сложение и умножение на число, вектор или матрицу и т.д. Также существуют готовые итерационные методы решения СЛАУ и их программные реализации, сохраняющие одновременно матрицу системы и решение в QTT-формате, такие как AMEN и TT-GMRES. Оба этих решателя используются в данной работе. Для предотвращения экспоненциального роста рангов в QTT представлении использовалась z-перестановка строк и столбцов матрицы. В качестве метода поиска численного решения взят итерационный метод Дирихле. Данный метод позволяет искать численное решение уравнения на отдельных подобластях задачи параллельно, после чего происходит согласование решения на границах подобластей. В результате выполнения данной работы был предложен итерационный алгоритм решения дифференциальных уравнений эллиптического типа. Следствием этого алгоритма является реализованный код решателя. Данный алгоритм демонстрирует ограниченное сверху константой число итераций во время поиска решения. Алгоритмическая сложность данного решателя O (︀nr2)︀, где r - это ранг в QTT представлении, n - число узлов сетки.