Оптимизация численных методов методами машинного обучения тема диссертации и автореферата по ВАК РФ 01.01.07, кандидат наук Катруца Александр Михайлович

• Катруца Александр Михайлович
• кандидат наук
• 2019

Оглавление диссертации кандидат наук Катруца Александр Михайлович

1.3 Выводы по главе

2 Оптимизация параметров многосеточного метода

2.1 Двухсеточный метод и стохастическая оценка спектрального радиуса

2.1.1 Двухсеточный метод

2.1.2 Задача минимизации спектрального радиуса

2.1.3 Вычисление градиентов для произведения трёх разреженных матриц вида RAP

2.2 Способы инициализации

2.2.1 Стандартная инициализация

2.2.2 Гомотопия

2.3 Вычислительная сложность

2.4 Вычислительный эксперимент

2.4.1 Обзор модельных задач

2.4.2 Уравнение Пуассона

2.4.3 Одномерное уравнение Гельмгольца

2.4.4 Сингулярно возмущённое уравнение конвекции-

диффузии

2.5 Выводы по главе

3 Стохастический подход к оптимизации предобусловливателя в методе сопряжённых градиентов

3.1 Средняя оценка сходимости

3.2 Вычислительная сложность процедуры оптимизации

3.3 Вычислительный эксперимент

3.3.1 Тестовая задача

3.3.2 Сравнение двух функционалов

3.3.3 Количество случайных начальных приближений п

3.4 Выводы по главе

4 Проблема мультиколлинеарности в задаче регрессии и методы решения этой проблемы

4.1 Задача снижения размерности в задаче регрессии

4.1.1 Проблема мультиколлинеарности

4.2 Решение проблемы мультиколлинеарности с помощью квадратичной оптимизации

4.2.1 Коэффициент корреляции

4.2.2 Взаимная информация

4.2.3 Нормализованная значимость столбца

4.2.4 Выпуклая релаксация задачи выбора столбцов матрицы плана

4.3 Тестовые выборки

4.4 Критерии качества

4.5 Вычислительный эксперимент

4.5.1 Данные для эксперимента

4.5.2 Сравнение с другими методами выбора столбцов матрицы плана

4.6 Выводы по главе

5 Быстрый и эффективный по памяти метод вычисления аппрок-

симации SimRank'a

5.1 Постановка задачи поиска значений SimRank'a

5.2 Малоранговая модель аппроксимации матрицы S

5.2.1 Связь с задачей снижения размерности

5.3 Ускорение вычислений с помощью вероятностного спектрального разложения

5.4 Сравнение с существующими методами

5.5 Вычислительный эксперимент

5.5.1 Эксперименты с графами из коллекции DIMACS10

5.5.2 Эксперимент с графом Simple English Wikipedia

5.6 Выводы по главе

Заключение

Список иллюстраций

Список таблиц

Список основных обозначений

Список литературы

Введение диссертации (часть автореферата) на тему «Оптимизация численных методов методами машинного обучения»

Введение

В настоящей работе предлагаются методы на основе подходов машинного обучения для оптимизации численных методов.

Актуальность исследования. Диссертационная работа посвящена разработке методов оптимизации значений параметров численных методов. Многие численные методы зависят от параметров, которые необходимо задавать перед запуском метода для решения конкретной задачи. Примерами подобных методов и соответствующими параметрами являются многосеточный метод [103], где параметрами являются операторы проекции и интерполяции между соседними уровнями иерархии сеток, а также параметр сглаживате-ля [92], предобусловленный метод сопряжённых градиентов [9] с предобуслов-ливателем неполным разложением Холецкого с релаксацией [10]. Данный пре-добусловливатель зависит от параметра релаксации, который необходимо задать перед использованием предобусловливателя. Также в диссертации рассматриваются другие численные методы и их параметризации. Зачастую выбор значений параметров численных методов существенно влияет на скорость их сходимости [98, 93], поэтому построение алгоритмов получения оптимальных значений параметров для численных методов является актуальной задачей. Под оптимальными значениями параметров будем понимать такие значения, которые обеспечивают наилучшую скорость сходимости численного метода.

У существующих подходов для определения значений параметров численных методов есть следующие недостатки. Во-первых, они обладают высокой вычислительной сложностью, так как зачастую основаны на переборе возможных значений параметра по сетке с большим числом точек [120]. Во-вторых, для некоторых подходящих значений параметров (таких что метод

сходится) отсутствуют гарантии оптимальности, то есть неизвестно можно ли улучшить данные значения параметров или нет [98, 92]. Также разработано множество алгоритмов для выбора значений параметров в случае решения задач определённого типа, однако эти алгоритмы не могут быть использованы для того же численного метода, используемого для решения задач другого типа [97]. Поэтому необходимо разработать универсальные методы выбора значений параметров численных методов, которые будут гарантировать оптимальность найденных значений.

Цель диссертационной работы.

1. Разработка новых подходов к ускорению алгоритмов решения систем линейных уравнений с разреженными матрицами

2. Разработка методов для решения проблемы мультиколлинеарности при решении задачи регрессии

3. Разработка новых быстрых методов приближённого вычисления меры похожести вершин в графе

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

Задачи работы.

1. Разработать общий подход к оптимизации численных методов с использованием формализма машинного обучения

2. Разработать и исследовать метод оптимизации значений параметров многосеточного метода решения систем линейных с разреженными матрицами

3. Разработать новый метод оптимизации предобусловливателей для метода сопряжённых градиентов

4. Разработать метод решения проблемы мультиколлинеарности для наиболее типичных конфигураций данных

5. Разработать быстрый и эффективный по памяти метод приближённого вычисления меры похожести между вершинами графа SimRank

Научная новизна. Предложены новые методы для поиска оптимальных значений параметров численных методов. Предложенные методы основаны на подходах машинного обучения и позволяют сделать вывод об оптимальности найденных значений параметров. Основная идея, лежащая в основе полученных результатов, заключается в записи численного метода как суперпозиции дифференцируемых функций, введения некоторого функционала качества и его оптимизация по отношению к параметрам численного метода. В работе исследованы свойства и методы решения полученных задач оптимизации для различных численных методов. Получены результаты о сложности вычисления стохастических градиентов в случае гладких целевых функций, а также приведены экспериментальные результаты по использованию безградиентных методов в случае недифференцируемых функционалов качества. Также были исследованы выпуклые релаксации задач дискретной оптимизации, возникающие при решении проблемы мультиколлинеарности. Получен метод малоранговой коррекции для приближённого вычисления величин SimRank'a между вершинами графа. Предложенный метод показал высокую эффективность по сравнению с другими подходами к решению этой задачи.

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

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

Теоретическая значимость работы В диссертационной работе представлена стохастическая оценка спектрального радиуса матрицы итераций для итерационного метода решения системы линейных уравнений. Эта оценка используется для оптимизации значений параметров многосеточного метода. Также исследована сложность вычисления градиентов этой оценки по параметрам многосеточного метода. Для метода сопряжённых градиентов введена новая концепция сходимости в среднем, которая является обобщением оценки, полученной для линейного итерационного метода. На основании этой концепции сходимости предложен алгоритм оптимизации предобусловливателей в методе сопряжённых градиентов. Далее приведён анализ решения проблемы мультиколлинеарности и установлен глобальный характер найденного решения для поставленной задачи квадратичной оптимизации. В заключении, для метода приближённого вычисления матрицы SimRank'a доказана теорема о представлении этой матрицы в виде ряда. Эта теорема позволяет ввести малоранговую поправку к первому члену этого ряда и использовать такое представления для приближённого вычисления SimRank'a.

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

1. Метод проверки оптимальности значений параметров многосеточного метода и их оптимизации

2. Метод оптимизации предобусловливателей в методе сопряжённых градиентов

3. Проанализирована проблема мультиколлинеарности в задаче регрессии и предложен новый метод для её решения

4. Метод приближённого вычисления меры похожести между вершинами графа SimRank

Апробация работы. Результаты, полученные в настоящей диссертации, имеют математическое обоснование, а также были экспериментально проверены на модельных и реальных задачах. Достоверность результатов также подтверждается публикациями в рецензируемых журналах, индексируемых Scopus и Web of Science. Результаты диссертации докладывались и обсуждались на следующих научных конференциях:

• Международная конференция «20th Conference of the International Federation of Operational Research Societies», 2014, Барселона

• 58-я научная конференция МФТИ, 2015, Москва

• 60-я научная конференция МФТИ, 2017, Москва

• 61-я научная конференция МФТИ, 2018, Москва

• Международная конференция «19th Copper Mountain Conference On Multigrid Methods», 2019, Copper Mountain

Публикации. Основные результаты настоящего диссертационного исследования опубликованы в следующих работах:

1. Работы, опубликованные в изданиях, входящих в перечень рецензируемых научных изданий, индексируемых Web of Science:

(a) Katrutsa A., Strijov V. Comprehensive study of feature selection methods to solve multicollinearity problem according to evaluation criteria // Expert Systems with Applications. — 2017. — Т. 76. — С. 1-11.

(b) Oseledets I. V., Ovchinnikov G. V., Katrutsa A. M. Fast, memory-efficient low-rank approximation of SimRank // Journal of Complex Networks. — 2016. — Т. 5. — №. 1. — С. 111-126.

(c) Katrutsa A. M., Strijov V. V. Stress test procedure for feature selection algorithms // Chemometrics and Intelligent Laboratory Systems. — 2015. -Т. 142. — С. 172-183.

(d) Katrutsa A., Daulbaev T., Oseledets I. Black-box learning of multigrid parameters //Journal of Computational and Applied Mathematics. — 2019. — https://doi.org/10.1016Zj.cam.2019.112524.

2. Работы, опубликованные в прочих изданиях:

(a) Оселедец И. В., Бочев М. А., Катруца А. М., Овчинников Г. B. Как оптимизировать предобусловливатели в методе сопряжённых градиентов: стохастический подход // Препринты Института прикладной математики им. М. В. Келдыша РАН. — 2018. — №. 164. — С. 1-26.

(b) Катруца А. М. Оптимизация параметров двухсеточного метода с помощью глубоких нейронных сетей // Труды 60-й научной конференции МФТИ, 2017

(c) Катруца А. М. Как оптимизировать предобуславливатели в методе сопряжённых градиентов: стохастический подход // Труды 61-й научной конференции МФТИ, 2018

Личный вклад автора. Диссертационное исследование является самостоятельным законченным трудом автора. Лично автором была предложена процедура вычисления градиентов по параметрам многосеточного метода в работе [54]. Также лично автором в работе [56] было предложено использовать подход квадратичного программирования для анализа мультиколлинеарно-сти. Постановка задачи в работах [54, 125, 82] была выполнена И.В. Оселедцем. Реализация алгоритмов, а также подготовка численных экспериментов в работах [54, 125, 82, 56, 55] были выполнены автором самостоятельно. Автором совместно с Г.В. Овчинниковым была получена теорема о разложении матрицы SimRank'a в ряд, вклад авторов равнозначен.

Структура работы. Диссертация состоит из оглавления, введения, пяти глав, заключения, списка иллюстраций, списка таблиц, перечня основных обо-

значений и списка литературы из 125 наименований. Полный объем диссертации составляет 115 страниц с 17 рисунками и 14 таблицами.

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

Глава 2 посвящена задаче оптимизации параметров многосеточного метода. Для этого вводится стохастическая оценка спектрального радиуса матрицы итераций на основе стохастической оценки следа матрицы. Многосеточный метод реализован с помощью функций, поддерживающих автоматическое вычисление градиентов. Таким образом, вычисления в многосеточном методе можно представить в виде графа вычислений. Это позволяет вычислять градиенты введённой стохастической оценки спектрального радиуса по параметрам многосеточного метода (операторам проекции, интерполяции и дэмпфи-рующего фактора) и определить такие параметры, при которых спектральный радиус принимает минимальное значение. Предложенный метод протестирован на двумерных граничных задачах Пуассона и сингулярно возмущённом уравнении конвекции-диффузии для набора сеток, а также для одномерного уравнения Гельмгольца с нулевыми граничными условиями. Во всех тестовых примерах предложенный метод показал улучшение скорости сходимости по сравнению с другими способами выбора параметров многосеточного метода.

В главе 3 представлена новая концепция сходимости метода сопряжённых градиентов, основанная на вычислении усреднённой нормы ошибки после заданного числа итераций. Эта оценка сходимости является обобщени-

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

Далее в главе 4 рассматривается проблема мультиколлинеарности в задаче регрессии. Для параметризации численного метода используется бинарное представление используемых столбцов матрицы плана. В качестве функционала качества предлагается использовать квадратичный функционал, в котором значения матрицы представляют попарные похожести между столбцами матрицы плана, а линейный член показывает важность каждого столбца при прогнозировании целевого вектора. Если матрица положительно полуопределённая (что выполнено, например, в случае использования корреляций Пирсона), то полученная задача оптимизации имеет выпуклую релаксацию, которая эффективно решается и, таким образом, восстанавливаем набор столбцов матрицы, которые приводят к повышению устойчивости и скорости работы метода решения задачи регрессии. Если матрица не является положительно полуопределённой, то можно рассмотреть выпуклую релаксацию для такой задачи с помощью теории двойственности. Предложенный метод превосходит другие способы выбора столбцов из набора мультиколлинеарных как по точности решения исходной задачи, так и по её устойчивости.

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

и высокая точность аппроксимации, получаемой с помощью предложенного метода на примере графов из коллекции DIMACS10 и графа, полученном из корпуса статей Simple English Wikipedia.

Благодарности. Прежде всего благодарность выражается Ивану Валерьевичу Оселедцу, научному руководителю автора диссертации. Подход Ивана Валерьевича к проведению исследований и умение понятно ставить задачи мотивировали автора к активной работе над диссертацией. Также автор благодарит соавторов Михаила Александровича Бочева и Георгия Викторовича Овчинникова за плодотворную совместную работу. Отдельная благодарность выражается Вадиму Викторовичу Стрижову, при научном руководстве которого началась научная деятельность автора.

Глава 1

Основные определения и обозначения

В данной главе вводятся основные понятия, используемые в последующих главах настоящей диссертационной работы. В частности, мы покажем, как задачу определения оптимальных параметров численных методов можно свести к задаче обучения с учителем — классической задаче машинного обучения [36, 15]. Также приведены аналогии между терминами, используемыми в машинном обучении и в вычислительной математике, в частности в области численных методов. Приведённые аналогии в дальнейшем будут использованы для демонстрации того, как работает изложенная концепция, приводящая к алгоритмам оптимизации численных методов с помощью методов машинного обучения.

Пусть дан некоторый набор пар (х-1>У1 = , то есть каждому объ-

екту е X ставится в соответствие некоторая метка у € У. Множества X и У соответственно обозначают множество объектов и множество меток. На данном этапе мы специально не конкретизируем вид множества объектов и меток более детально, и будем это делать отдельно в каждой последующей главе, тем самым демонстрируя универсальность предлагаемого подхода. Тогда задача обучения с учителем состоит в том, чтобы по данному набору из Ы3 пар объектов и меток найти некоторую функцию /* : X ^ У, такую что для любого объекта из множества X она возвращала бы правильную метку у е У. В машинном обучении функцию / : X ^ У также называют моделью. Для

1.1

упрощения поиска оптимальной модели /* вводят предположение о том, что искомая модель лежит в некотором параметрическом семействе Т. Тогда для поиска /* необходимо ввести некоторую функцию потерь I: У х У ^ К, такую что

- 1 —

г = а^ш1и —Уе (/ (х1 ), (1.1)

г =1

то есть функция I должна быть равна нулю, если функция / возвращает правильную метку, и больше нуля, если неправильную. Также учитывая, что семейство Т параметрическое, задачу (1.1) можно переписать в виде

1 —

ш* = а^шт — У €(/(ш | хг),уг), (1.2)

где № — множество параметров, соответствующих семейству функций Т. Запись / (ш | XI) означает, что функция / зависит от ш как от параметра при данном объекте х^. Задачу (1.2) также называют задачей минимизации эмпирического риска [106].

Л.

К сожалению, точное решение /* задачи (1.1) не всегда отвечает изначальной цели получить такую функцию /*, что для любого объекта возвращаемая метка будет правильная. Явление, при котором среднее значение функции потерь на данном наборе из — пар (обучающей выборке) мало, а на любом другом наборе пар из того же множества X х У (тестовой выборке) существенно больше, называется переобучением [100]. Существует множество способов бороться с этим явлением [29, 91, 30], и на данный момент оно не является непреодолимым препятствием при разработке методов для решения задачи обучения с учителем.

Таким образом, для постановки задачи обучения с учителем нужна обучающая выборка из объектов х^ и меток у, параметрическая функция / (ш | х) и функция потерь I, которая будет оценивать качество параметров w. Предполагая, что параметрическое семейство и функция потерь не приводят к переобучению, получим, что решение задачи (1.2) даёт оптимальные параметры для предсказания метки у е У по некоторому объекту X е X.

1.1.1 Задача поиска оптимальных значений параметров численных методов как задача обучения с учителем

Предположим, численный метод зависит от параметров V и результат его выполнения через ктах итераций можно представить как значение некоторой функции вида g(V | х0,ктах,V), где х0 — начальное приближение, ктах — максимальное число итераций, V — это множество всех параметров, которые задают задачу, решаемую численным методом. Каждому начальному приближению соответствует приближение %к, полученное после выполнения к итераций численного метода. В то же время для данной задачи V существует точное решение х*, которое должно быть приближено с помощью %к после достаточно большого числа итераций. Одним из основным свойств численных методов, является скорость их сходимости, то есть то насколько быстро приближение %к сходится к точному решению х* после выполнения к итераций [78, 93, 104]. Скорость сходимости численных методов зачастую зависит от параметров V, используемых для решения задачи, описанной множеством V. Таким образом, если мы введём некоторую функцию потерь С, отражающую скорость сходимости численного метода для данного начального приближения х0, то сможем записать следующую задачу

*

1 \ '

V = а^тт С^(V | х0°Дтах, Р),х*), (1.3)

г = 1

veV ^в

л) (г) ■

где V — пространство параметров численного метода, х0 — г-ое начальное приближение. В последующих главах для каждого рассмотренного численного метода будем указывать вид функции С, её свойства, а также свойства функции g, которые напрямую влияют на выбор способа решения задачи (1.3). Также будет рассмотрен вопрос о способе задания набора начальных приближений {х0 ,...,х0 }.

1.2 Подходы к решению задачи поиска оптимальных значений параметров численных методов

В зависимости от вида функции /, выбранной функции ошибки С, а также размерности пространства параметров решать задачу поиска оптимальных параметров необходимо различными методами. Например, если размерность пространства параметров невелика, например численный метод зависит от скаляра, который принадлежит известному интервалу, то решение задачи (1.3) можно получить с помощью безградиентных методов оптимизации [23].

Если же размерность пространства параметров велика и параметры принимают вещественные значения, то необходимо использовать градиентные методы оптимизации [28, 74, 21]. Заметим, что любой численный метод состоит из элементарных операций, поэтому функцию g можно представить в виде суперпозиции этих элементарных операций

g = gl ◦ g2 ◦ • • • ◦ gd■

Такое представление и техника автоматического дифференцирования, реализованная во многих пакетах [67, 99, 101, 6] позволяют вычислить градиент от функции С по параметрам V для каждого начального приближения. Это замечательное свойство позволяет воспользоваться всеми преимуществами градиентных методов оптимизации и получить локально оптимальные значения параметров V. В частности, гарантией сходимости к локальному минимуму, качество которого может быть улучшено с помощью специального выбора начального приближения для параметров численного метода v0. Отметим, что подобная техника используется в алгоритмах обучения глубоких нейронных сетей [7].

Ещё один случай — это пространство параметров большой размерности, но состоящее только из булевых векторов, то есть векторов из нулей и единиц. Такие задачи называются задачами дискретной оптимизации [85] и в общем случае являются ^-сложными [65]. Поэтому в этом случае предлагается использовать выпуклую релаксацию задачи (1.3), которая будет гарантировано

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

В последующих главах будут приведены конкретные примеры численных методов и их параметризаций, то есть будет дано определение множеству V и будет уточнено использование параметров в численных методах. Приведённые параметризации будут приводить к задачам (1.3), для решения которых потребуется использование одного из вышеуказанных подходов.

1.3 Выводы по главе

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

Глава 2

Оптимизация параметров многосеточного метода

В этой главе мы исследуем оптимальность параметров, используемых в многосеточных методах (геометрическом и алгебраическом), и предлагаем метод их оптимизации. Многосеточный метод часто является наилучшим методом решения больших разреженных систем линейных уравнений, возникающих при решении дискретизованных уравнений в частных производных [43, 20]. Главный вопрос при применении многосеточных методов — это задание операторов интерполяции и операторов проекции. Эти операторы задаются исходя из априорных знаний о структуре системы или различных эвристик [43].

Для решения вопроса о выборе этих параметров для решения данной линейной системы с матрицей A мы предлагаем минимизировать спектральный радиус матрицы итерации многосеточного метода, которая зависит от операторов интерполяции, проекции и сглаживателя. Однако, задача минимизации спектрального радиуса является негладкой, а вычисление субградиента целевой функции требует знания главного левого и правого собственных векторов, вычисление которых может быть слишком затратным [75]. Поэтому вместо минимизации спектрального радиуса мы предлагаем минимизировать его стохастическую оценку сверху, полученную с помощью формулы Гельфанда [57]. После получения гладкой целевой функции, которая корректно отражает сходимость многосеточного метода, мы разработали метод Deep Multigrid (DMG), который определяет оптимальные параметры многосеточного метода с помощью минимизации введённой стохастической оценки спектрального радиу-

са. Мы показали, как переписать задачу минимизации, чтобы можно было применить методы, основанные на использовании стохастического градиента целевой функции. Все современные фреймворки для машинного обучения (Аи^гаё [67], TensorFlow [99], ^еапо [101], РуТогЛ [6] и другие) обладают необходимыми инструментами для реализации многосеточного метода. Достоинством такой реализации является возможность автоматически вычислять градиенты целевой функции по заданным переменным с помощью техники автоматического дифференцирования [11].

Список литературы диссертационного исследования кандидат наук Катруца Александр Михайлович, 2019 год

Литература

1. ARPACK: a collection of subroutines designed to solve large scale eigenvalue problems. — http://www.caam.rice.edu/software/ARPACK/.

2. Adaptive algebraic multigrid / Marian Brezina, R Falgout, Scott MacLachlan et al. // SIAM Journal on Scientific Computing. — 2006. — Vol. 27, no. 4. — P. 1261-1286.

3. Adaptive smoothed aggregation (a SA) / Marian Brezina, R Falgout, Scott MacLachlan et al. // SIAM Journal on Scientific Computing. — 2004. — Vol. 25, no. 6. — P. 1896-1920.

4. An evaluation of SimRank and Personalized PageRank to build a recommender system for the Web of Data / Phuong Nguyen, Paolo Tomeo, Tommaso Di Noia, Eugenio Di Sciascio // Proceedings of the 24th International Conference on World Wide Web / ACM. — 2015. — P. 1477-1482.

5. Assessing single-pair similarity over graphs by aggregating first-meeting probabilities / Jun He, Hongyan Liu, Jeffrey Xu Yu et al. // Information Systems. — 2014. — Vol. 42. — P. 107-122.

6. Automatic differentiation in PyTorch / Adam Paszke, Sam Gross, Soumith Chin-tala et al. — 2017.

7. Automatic differentiation in machine learning: a survey / Atilim Gunes Baydin, Barak A Pearlmutter, Alexey Andreyevich Radul, Jeffrey Mark Siskind // Journal of machine learning research. — 2018. — Vol. 18, no. 153.

8. Avron Haim, Toledo Sivan. Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix // Journal of the ACM (JACM). — 2011. — Vol. 58, no. 2. — P. 8.

9. AxelssonOwe. Iterative solution methods. — Cambridge : Cambridge University Press, 1994.

10. Axelsson Owe, Lindskog Gunhild. On the eigenvalue distribution of a class of preconditioning methods // Numerische Mathematik. — 1986. — Vol. 48, no. 5. — P. 479-498.

11. Baur Walter, Strassen Volker. The complexity of partial derivatives // Theoretical computer science. — 1983. — Vol. 22, no. 3. — P. 317-330.

12. Bell W. N., Olson L. N., Schroder J. B. PyAMG: Algebraic Multigrid Solvers in Python v3.0. — 2015.— Release 3.2. URL: https://github.com/ pyamg/pyamg.

13. Benner Peter, Feng Lihong. Recycling Krylov subspaces for solving linear systems with successively changing right-hand sides arising in model reduction // Model Reduction for Circuit Simulation. — Springer, 2011. — P. 125-140.

14. Benzi M. Preconditioning Techniques for Large Linear Systems: A Survey //Journal of Computational Physics. — 2002. — Vol. 182. — P. 418-477.

15. Bishop Christopher M. Pattern recognition and machine learning.— springer, 2006.

16. Bochev Mikhail A., Krukier Lev A. Iterative solution of strongly nonsymmetric systems of linear algebraic equations // Russian Comput. Mathematics and Math. Physics. — 1997. — Vol. 37, no. 11. — P. 1241-1251.

17. Bootstrap AMG / Achi Brandt, J Brannick, Karsten Kahl, Irene Livshits // SIAM Journal on Scientific Computing. — 2011. — Vol. 33, no. 2. — P. 612-632.

18. Botchev Mike A, Golub Gene H. A class of nonsymmetric preconditioners for saddle point problems // SIAM Journal on Matrix Analysis and Applications. — 2006. — Vol. 27, no. 4. — P. 1125-1149.

19. Brent Richard P. Algorithms for minimization without derivatives.— Courier Corporation, 2013.

20. Briggs William L, Henson Van Emden, McCormick Steve F. A multigrid tutorial. - SIAM, 2000.

21. Bubeck, Sébastien and others. Convex optimization: Algorithms and complexity // Foundations and Trends® in Machine Learning. — 2015. — Vol. 8, no. 3-4. — P. 231-357.

22. Computing Reduced Order Models via Inner-Outer Krylov Recycling in Diffuse Optical Tomography / Meghan O'Connell, Misha E Kilmer, Eric de Sturler, Serkan Gugercin // SIAM Journal on Scientific Computing. — 2017. — Vol. 39, no. 2. — P. B272-B297.

23. Conn Andrew R, Scheinberg Katya, Vicente Luis N. Introduction to derivativefree optimization. — SIAM, 2009. — Vol. 8.

24. Cortes Corinna, Mohri Mehryar, Talwalkar Ameet. On the impact of kernel approximation on learning accuracy // Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics. — 2010. — P. 113-120.

25. Dai Ruxin, Wang Yin, Zhang Jun. Fast and high accuracy multiscale multi-grid method with multiple coarse grid updating strategy for the 3D convection-diffusion equation // Computers & Mathematics with Applications. — 2013. — Vol. 66, no. 4. — P. 542-559.

26. De Zeeuw Paulus Maria. Matrix-dependent prolongations and restrictions in a blackbox multigrid solver // Journal of Computational and Applied Mathematics. — 1990. — Vol. 33, no. 1. — P. 1-27.

27. Dendy JE. Black box multigrid // Journal of Computational Physics. — 1982. — Vol. 48, no. 3. — P. 366-386.

28. Devolder, Olivier and Glineur, François and Nesterov, Yurii. First-order methods of smooth convex optimization with inexact oracle // Mathematical Programming. — 2014. — Vol. 146, no. 1-2. — P. 37-75.

29. Dietterich Thomas G. Ensemble methods in machine learning // International workshop on multiple classifier systems / Springer. — 2000. — P. 1-15.

30. Dropout: a simple way to prevent neural networks from overfitting / Nitish Sri-vastava, Geoffrey Hinton, Alex Krizhevsky et al. // The journal of machine learning research. — 2014. — Vol. 15, no. 1. — P. 1929-1958.

31. Eckart Carl, Young Gale. The approximation of one matrix by another of lower rank // Psychometrika. — 1936. — Vol. 1, no. 3. — P. 211-218.

32. Efficient Search Algorithm for SimRank / Makoto Onizuka, Yasuhiro Fujiwara, Hiroaki Shiokawa, Makoto Nakatsuji // Proceedings of the 2013 IEEE International Conference on Data Engineering (ICDE 2013). — ICDE '13. — Washington, DC, USA : IEEE Computer Society, 2013.— P. 589-600.— URL: http: //dx.doi.org/10.1109/ICDE.2013.6544858.

33. El-Dereny M, Rashwan NI. Solving multicollinearity problem using ridge regression models // International Journal of Contemporary Mathematical Sciences. — 2011. — Vol. 6. — P. 585-600.

34. Fast Computation of SimRank for Static and Dynamic Information Networks / Cuiping Li, Jiawei Han, Guoming He et al. // Proceedings of the 13th International Conference on Extending Database Technology. — EDBT '10. — New York, NY, USA: ACM, 2010. — P. 465-476. — URL: http://doi.acm.org/10. 1145/1739041.1739098.

35. Fogaras Daniel, Racz Balazs. Scaling link-based similarity search // Proceedings of the 14th international conference on World Wide Web / ACM. — 2005. — P. 641-650.

36. Friedman Jerome, Hastie Trevor, Tibshirani Robert. The elements of statistical learning. — Springer series in statistics New York, 2001. — Vol. 1.

37. Ghamisi Pedram, Benediktsson Jon Atli. Feature selection based on hybridization of genetic algorithm and particle swarm optimization // IEEE Geoscience and Remote Sensing Letters. — 2015. — Vol. 12, no. 2. — P. 309-313.

Gilmour Steven G. The Interpretation of Mallows's Cp-Statistic // Journal of the Royal Statistical Society. Series D (The Statistician). — 1996. — Vol. 45, no. 1. — P. 49-56.

39. Golub Gene H, Van Loan Charles F. Matrix computations. — 3 edition. — JHU Press, 2012.

40. Grasedyck Lars, Wang Lu, Xu Jinchao. A nearly optimal multigrid method for general unstructured grids//Numerische Mathematik. — 2016.— Vol. 134, no. 3. — P. 637-666.

41. Greenbaum Anne. Iterative methods for solving linear systems. — SIAM, 1997. — Vol. 17.

42. Guyon Isabelle. An introduction to variable and feature selection // Journal of Machine Learning Research. — 2003. — Vol. 3. — P. 1157-1182.

43. Hackbusch Wolfgang. Multi-grid methods and applications. — Springer Science & Business Media, 2013. — Vol. 4.

44. Halko N., Martinsson P., Tropp J. Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions // SIAM Review.— 2011.— Vol. 53, no. 2.— P. 217-288.— http://dx.doi.org/10.1137/090771806.

45. Hall Mark A. Correlation-based feature selection for machine learning : Ph.D. thesis / Mark A Hall; The University of Waikato. — 1999.

46. Hammarling Sven. Numerical solution of the discrete-time, convergent, nonnegative definite Lyapunov equation // Systems & Control Letters.— 1991.— Vol. 17, no. 2. — P. 137-139.

47. Hemker PW. On the order of prolongations and restrictions in multigrid procedures //Journal of Computational and Applied Mathematics. — 1990. — Vol. 32, no. 3. — P. 423-429.

48. Hestenes Magnus Rudolph, Stiefel Eduard. Methods of conjugate gradients for solving linear systems. — NBS Washington, DC, 1952. — Vol. 49.

49. Hutchinson Michael F. A stochastic estimator of the trace of the influence matrix for Laplacian smoothing splines // Communications in Statistics-Simulation and Computation. — 1990. — Vol. 19, no. 2. — P. 433-450.

50. Jeh Glen, Widom Jennifer. SimRank: A Measure of Structural-context Similarity // Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. — KDD '02. — New York, NY, USA : ACM, 2002.— P. 538-543.— URL: http://doi.acm.org/10.1145/ 775047.775126.

51. Jenatton Rodolphe, Audibert Jean-Yves, Bach Francis. Structured variable selection with sparsity-inducing norms // Journal of Machine Learning Research. — 2011. — Vol. 12, no. Oct. — P. 2777-2824.

52. Kaporin Igor. Scaling, preconditioning, and superlinear convergence in GMRES-type iterations // Matrix Methods: Theory, Algorithms and Applications: Dedicated to the Memory of Gene Golub. — World Scientific, 2010. — P. 273-295.

53. Kaporin I E. New convergence results and preconditioning strategies for the conjugate gradient method // Numerical Linear Algebra with Applications. — 1994. — Vol. 1, no. 2. — P. 179-210.

54. Katrutsa Alexandr, Daulbaev Talgat, Oseledets Ivan. Black-box learning of multigrid parameters // Journal of Computational and Applied Mathematics. — 2019. — https://doi.org/10.1016/j.cam.2019.112524.

55. Katrutsa AM, Strijov VV. Stress test procedure for feature selection algorithms // Chemometrics and Intelligent Laboratory Systems. — 2015. — Vol. 142. — P. 172183.

56. Katrutsa Alexandr, Strijov Vadim. Comprehensive study of feature selection methods to solve multicollinearity problem according to evaluation criteria // Expert Systems with Applications. — 2017. — Vol. 76. — P. 1-11.

57. Kozyakin Victor. On accuracy of approximation of the spectral radius by the Gelfand formula//Linear Algebra and its Applications. — 2009.— Vol. 431, no. 11. — P. 2134-2141.

58. Kressner Daniel, Vandereycken Bart. Subspace methods for computing the pseudospectral abscissa and the stability radius // SIAM Journal on Matrix Analysis and Applications. — 2014. — Vol. 35, no. 1. — P. 292-313.

59. Kusumoto Mitsuru, Maehara Takanori, Kawarabayashi Ken-ichi. Scalable Similarity Search for SimRank // Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. — SIGMOD '14. — New York, NY, USA : ACM, 2014.— P. 325-336.— URL: http://doi.acm.org.sci-hub. org/10.1145/2588555.2610526.

60. Ladha L, Deepa T. Feature selection methods and algorithms // International Journal on Computer Science and Engineering. — 2011. — Vol. 3, no. 5. — P. 17871797.

61. Leardi Riccardo. Genetic algorithms in chemometrics and chemistry: a review // Journal of chemometrics. — 2001. — Vol. 15, no. 7. — P. 559-569.

62. Learning to Optimize Multigrid PDE Solvers / Daniel Greenfeld, Meirav Galun, Ronen Basri et al. // International Conference on Machine Learning. — 2019. — P. 2415-2423.

63. Learning to Rank Using Gradient Descent / Chris Burges, Tal Shaked, Erin Renshaw et al. // Proceedings of the 22nd International Conference on Machine Learning. — ICML '05. — New York, NY, USA : ACM, 2005. — P. 89-96. — URL: http://doi.acm.org/10.1145/1102351.1102363.

64. Lee Pei, Lakshmanan Laks VS, Yu Jeffrey Xu. On top-k structural similarity search // Data Engineering (ICDE), 2012 IEEE 28th International Conference on / IEEE. — 2012. — P. 774-785.

65. Lenstra Jan K, Kan AHG Rinnooy. Computational complexity of discrete optimization problems // Annals of Discrete Mathematics. — Elsevier, 1979. — Vol. 4. — P. 121-140.

66. Livshits Ira. A scalable multigrid method for solving indefinite Helmholtz equations with constant wave numbers // Numerical Linear Algebra with Applications. — 2014. — Vol. 21, no. 2. — P. 177-193.

67. Maclaurin Dougal, Duvenaud David, Adams Ryan P. Autograd: Effortless gradients in numpy // ICML 2015 AutoML Workshop. — 2015.

68. Mapreduce-based SimRank computation and its application in social recom-mender system / Lina Li, Cuiping Li, Hong Chen, Xiaoyong Du // Big Data (BigData Congress), 2013 IEEE International Congress on / IEEE. — 2013. — P. 133140.

69. McQuarrie Allan DR, Tsai Chih-Ling. Regression and time series model selection. — World Scientific, 1998.

70. Mengi Emre, Yildirim E Alper, Kiliç Mustafa. Numerical optimization of eigenvalues of Hermitian matrix functions // SIAM Journal on Matrix Analysis and Applications. — 2014. — Vol. 35, no. 2. — P. 699-724.

71. Meurant Gerard. Computer solution of large linear systems. — Elsevier, 1999. — Vol. 28.

72. Meurant Gérard. The Lanczos and Conjugate Gradient Algorithms: from theory to finite precision computations. — SIAM, 2006.

73. Nesterov Yurii. Smoothing technique and its applications in semidefinite optimization // Mathematical Programming. — 2007. — Vol. 110, no. 2. — P. 245-259.

74. Nesterov Yurii. Lectures on convex optimization. — Springer, 2018. — Vol. 137.

75. Nesterov Yurii, Protasov Vladimir Yu. Optimizing the spectral radius // SIAM Journal on Matrix Analysis and Applications. — 2013. — Vol. 34, no. 3. — P. 9991013.

76. Normalized mutual information feature selection / Pablo A Estévez, Michel Tes-mer, Claudio A Perez, Jacek M Zurada // Neural Networks, IEEE Transactions on. — 2009. — Vol. 20, no. 2. — P. 189-201.

77. Numerical Linear Algebra for High-Performance Computers / Jack J. Dongarra, Iain S. Duff, Danny C. Sorensen, Henk A. van der Vorst. — Philadelphia, PA : SIAM, 1998. — P. 342.

78. Olshanskii Maxim A, Tyrtyshnikov Eugene E. Iterative methods for linear systems: theory and applications. — SIAM, 2014.

79. Olshanskii Maxim A, Tyrtyshnikov Eugene E. Iterative methods for linear systems: theory and applications. — SIAM, 2014.

80. Olson Luke N, Schroder Jacob B, Tuminaro Raymond S. A general interpolation strategy for algebraic multigrid using energy minimization // SIAM Journal on Scientific Computing. — 2011. — Vol. 33, no. 2. — P. 966-991.

81. Oosterlee Cornelis W, Wienands Roman. A genetic search for optimal multi-grid components within a Fourier analysis setting // SIAM Journal on Scientific Computing. — 2003. — Vol. 24, no. 3. — P. 924-944.

82. Oseledets I.V., Ovchinnikov G.V., Katrutsa A.M. Fast, memory-efficient low-rank approximation of SimRank // Journal of Complex Networks. — 2016. — Vol. 5, no. 1. — P. 111-126.

83. Papailiopoulos Dimitris, Dimakis Alexandros, Korokythakis Stavros. Sparse PCA through low-rank approximations // International Conference on Machine Learning. — 2013. — P. 747-755.

84. Parameter estimates for the Relaxed Dimensional Factorization precondi-tioner and application to hemodynamics / Michele Benzi, Simone Deparis, Gwenol Grandperrin, Alfio Quarteroni // Computer Methods in Applied Mechanics and Engineering. — 2016. — Vol. 300. — P. 129-145.

85. Parker R Gary, Rardin Ronald L. Discrete optimization. — Elsevier, 2014.

86. Multicollinearity: Causes, Effects and Remedies : Rep. / Working paper, unknown date. Accessed Apr. 23, 2013, http://pb8.ru/7hy ; Executor: Ranjit Kumar Paul : 2006.

87. Paul Sujoy, Das Swagatam. Simultaneous feature selection and weighting-An evolutionary multi-objective optimization approach // Pattern Recognition Letters. — 2015. — Vol. 65. — P. 51-59.

88. Peng Hanchuan, Long Fuhui, Ding Chris. Feature selection based on mutual information criteria of max-dependency, max-relevance, and min-redundancy // IEEE Transactions on pattern analysis and machine intelligence. — 2005. — Vol. 27, no. 8. — P. 1226-1238.

89. Picard Richard R, Cook R Dennis. Cross-validation of regression models // Journal of the American Statistical Association. — 1984. — Vol. 79, no. 387. — P. 575583.

90. Recycling Krylov subspaces for CFD applications and a new hybrid recycling solver / Amit Amritkar, Eric de Sturler, Katarzyna Swirydowicz et al. // Journal of Computational Physics. — 2015. — Vol. 303. — P. 222-237.

91. Reducing overfitting in deep networks by decorrelating representations / Michael Cogswell, Faruk Ahmed, Ross Girshick et al. // arXiv preprint arXiv:1511.06068. — 2015.

92. Ruge John W, Stüben Klaus. Algebraic multigrid // Multigrid methods. — 1987. — Vol. 3, no. 13. — P. 73-130.

93. Saad Yousef. Iterative Methods for Sparse Linear Systems. — 2d edition. — SIAM, 2003.— Available from http://www-users.cs.umn.edu/~saad/ books.html.

94. Saad Youcef, Schultz Martin H. GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems // SIAM Journal on Scientific and Statistical Computing. — 1986. — Vol. 7, no. 3. — P. 856-869.

95. Sarkar Purnamrita, Moore Andrew W. Random walks in social networks and their applications: a survey // Social Network Data Analytics. — Springer, 2011. — P. 43-77.

96. Schölkopf Bernhard, Smola Alexander, Müller Klaus-Robert. Kernel principal component analysis // International onference on artificial neural networks / Springer. — 1997. — P. 583-588.

97. Stolk Christiaan C, Ahmed Mostak, Bhowmik Samir Kumar. A multigrid method for the Helmholtz equation with optimized coarse grid corrections // SIAM Journal on Scientific Computing. — 2014. — Vol. 36, no. 6. — P. A2819-A2841.

98. Stüben Klaus. A review of algebraic multigrid // Journal of Computational and Applied Mathematics. — 2001. — Vol. 128, no. 1. — P. 281-309.

99. TensorFlow: A System for Large-Scale Machine Learning. / Martin Abadi, Paul Barham, Jianmin Chen et al. // OSDI. — Vol. 16. — 2016. — P. 265-283.

100. Tetko Igor V, Livingstone David J, Luik Alexander I. Neural network studies. 1. Comparison of overfitting and overtraining // Journal of chemical information and computer sciences. — 1995. — Vol. 35, no. 5. — P. 826-833.

101. Theano Development Team. Theano: A Python framework for fast computation of mathematical expressions // arXiv e-prints. — 2016. — Vol. abs/1605.02688. — URL: http://arxiv.org/abs/1605.02688.

102. Tibshirani Robert. Regression Shrinkage and Selection Via the Lasso // Journal of the Royal Statistical Society, Series B. — 1994. — Vol. 58. — P. 267-288.

103. Trottenberg Ulrich, Oosterlee Cornelius W, Schuller Anton. Multigrid. — Academic press, 2000.

104. Tyrtyshnikov Eugene E. A brief introduction to numerical analysis. — Springer Science & Business Media, 2012.

105. Using link-based content analysis to measure document similarity effectively / Pei Li, Zhixu Li, Hongyan Liu et al. // Advances in Data and Web Management. — Springer, 2009. — P. 455-467.

106. Vapnik Vladimir. The nature of statistical learning theory. — Springer science & business media, 2013.

107. Varga Richard S. Matrix Iterative Analysis. — Prentice-Hall, 1962.

108. Watson Layne T, Haftka Raphael T. Modern homotopy methods in optimization // Computer Methods in Applied Mechanics and Engineering. — 1989. — Vol. 74, no. 3. — P. 289-305.

109. Williams Kyle, Wu Jian, Giles C Lee. SimSeerX: a similar document search engine // Proceedings of the 2014 ACM symposium on Document engineering / ACM. — 2014. — P. 143-146.

110. Wold Svante, Esbensen Kim, Geladi Paul. Principal component analysis // Chemometrics and intelligent laboratory systems. — 1987. — Vol. 2, no. 1-3. — P. 37-52.

111. Xu Jinchao. The auxiliary space method and optimal multigrid preconditioning techniques for unstructured grids // Computing. — 1996. — Vol. 56, no. 3. — P. 215-235.

112. Yserentant Harry. Old and new convergence proofs for multigrid methods // Acta numerica. — 1993. — Vol. 2. — P. 285-326.

113. Yu Weiren, Lin Xuemin, Zhang Wenjie. Towards efficient SimRank computation on large networks // Data Engineering (ICDE), 2013 IEEE 29th International Conference on / IEEE. — 2013. — P. 601-612.

114. Yu Weiren, McCann Julie A. Efficient Partial-Pairs SimRank Search on Large Networks // Proceedings of the VLDB Endowment. — 2015. — Vol. 8, no. 5.

115. Zhang Kai, Tsang Ivor W, Kwok James T. Improved Nystrom low-rank approximation and error analysis // Proceedings of the 25th International Conference on Machine learning / ACM. — 2008. — P. 1232-1239.

116. Zou Hui, Hastie Trevor. Regularization and variable selection via the Elastic Net // Journal of the Royal Statistical Society, Series B. — 2005. — Vol. 67. — P. 301-320.

117. A genetic algorithm-based feature selection / Babatunde Oluleye, L Armstrong, Jinsong Leng, D Diepeveen // British Journal of Mathematics & Computer Science. — 2014. — P. In-Press.

118. A hybrid multigrid method for convection-diffusion problems / S Chaabane Khe-lifi, Namane Méchitoua, Frank Hulsemann, Frédéric Magoulès //Journal of Computational and Applied Mathematics. — 2014. — Vol. 259. — P. 711-719.

119. A measure of similarity between graph vertices: Applications to synonym extraction and web searching / Vincent D Blondel, Anahi Gajardo, Maureen Hey-mans et al. // SIAM Review. — 2004. — Vol. 46, no. 4. — P. 647-666.

120. van den Eshof Jasper, Hochbruck Marlis. Preconditioning Lanczos approximations to the matrix exponential // SIAM Journal on Scientific Computing. — 2006. — Vol. 27, no. 4. — P. 1438-1457.

121. van der Sluis Abraham, van der Vorst Henk A. The Rate of Convergence of Conjugate Gradients // Numer. Math. — 1986. — Vol. 48. — P. 543-560.

122. van der Vorst Henk A. ICCG and related methods for 3D problems on vector computers // Computer Physics Communications. — 1989. — Vol. 53, no. 1-3. — P. 223-235.

123. van der Vorst Henk A. Iterative Krylov methods for large linear systems. — Cambridge University Press, 2003.

124. van der Vorst Henk A., Vuik Cees. The Superlinear Convergence of GMRES //J. Comput. Appl. Math. — 1993. — Vol. 48. — P. 327-341.

125. Как оптимизировать предобусловливатели в методе сопряженных градиентов: стохастический подход / Иван Валерьевич Оселедец, Михаил Александрович Бочев, Александр Михайлович Катруца, Георгий Викторович Овчинников // Препринты Института прикладной математики им. МВ Келдыша РАН. — 2018. — no. 164. — P. 1-26.