Исследование скорости сходимости ускоренных блочных вариантов строчно-ориентированной формы регуляризованного алгоритма Качмажа

全文:

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

Цель — разработка, исследование и программная реализация ускоренных блочных вариантов строчно-ориентированной формы регуляризованного алгоритма Качмажа.

Методы. Для регуляризованной формы алгоритма Качмажа ключевым этапом является вычисление псевдообратной матрицы, что определяет общую вычислительную сложность метода. В работе [1] используется итерационный алгоритм Бен-Израэля для вычисления псевдообратной матрицы:

$X_{k+1}=X_k[2E-A{X}_k],k=0,1,2,\dots$ (1)

Этот метод учитывает специфическую структуру расширенной матрицы системы [2] и позволяет эффективно использовать современные высокопроизводительные вычислительные платформы.

Рассмотрим методы ускорения процедуры вычисления псевдообратной матрицы. Так, Тутуниан и Солеймани [3] предложили метод четвертого порядка, требующий пять операций умножения матриц:

$X_{k+1}=0.5X_k(9E-A{X}_k(16E-A{X}_k(14E-A{X}_k(6E-A{X}_k\left)\right)\left)\right)$. (2)

Кришнамурти и Сен [3] представили альтернативный метод четвертого порядка, включающий четыре операции умножения матриц:

$X_{k+1}=X_k(E+Y_k(E+Y_k(E+Y_k)\left)\right),Y_k=E-A{X}_k$. (3)

Другим эффективным способом ускорения сходимости алгоритма является этап препроцессинга. Линейную систему $Au=f$ можно преобразовать в эквивалентную систему $QAu=Qf$. При этом матрица $Q$ определяется как:

$Q=HD$,

где $H$ — матрица Адамара, $D$ — диагональная матрица размером $m\times m$, элементы которой случайным образом принимают значения $\pm 1/\sqrt{m}$.

Результаты. На рис. 1 представлены графики сравнения времени вычисления псевдообратной матрицы для методов (1)–(3), примененных к матрице $A^{4096\times 4096}$ на CPU и GPU.

Рис. 1. Тестовая задача c матрицей ${\mathit{A}}^{\mathbf{4096}\mathbf{\times }\mathbf{4096}}$

На рис. 2 приведены графики, демонстрирующие сравнение относительной ошибки и времени выполнения классического алгоритма и его версии с препроцессингом для матрицы $A^{4096\times 4096}$.

Рис. 2. Тестовая задача c матрицей ${\mathit{A}}^{\mathbf{4096}\mathbf{\times }\mathbf{4096}}$. Число блоков 4

Выводы. Анализ методов ускорения вычислительного процесса показывает, что применение методов (2) и (3) обеспечивает лишь умеренное сокращение времени вычисления псевдообратной матрицы, но требует дополнительных вычислительных ресурсов. Это ограничивает их эффективность при обработке больших объемов данных и высокоразмерных систем. Напротив, алгоритм с этапом препроцессинга демонстрирует существенное преимущество, снижая время выполнения расчетов в 14,5 раз. Этот результат подтверждает, что предварительная обработка данных и оптимизация вычислительных структур играют ключевую роль в повышении скорости работы алгоритма.

作者简介

编辑信件的主要联系方式.
Email: sad17052001@gmail.com

студент, группа 2-ИАИТ-110М, институт автоматики и информационных технологий

参考

补充文件

附件文件

动作

1. JATS XML

下载

2. Рис. 1. Тестовая задача c матрицей A4096×4096

下载 (93KB)

索引源数据

3. Рис. 2. Тестовая задача c матрицей A4096×4096. Число блоков 4

下载 (107KB)

索引源数据