Алгоритм Ланцоша является прямым алгоритмом разработан Ланцошем , что является адаптацией силовых методов , чтобы найти«самый полезный» (тенденцию к экстремальным высоких / низких) собственных значений и собственных векторов А.Н. Эрмитова матрица , где часто, но не обязательно, намного меньше, чем . [1] Несмотря на то, что метод, в принципе, эффективен с точки зрения вычислений, изначально сформулированный метод не был полезен из-за его численной нестабильности .
В 1970 году Оялво и Ньюман показали, как сделать этот метод численно устойчивым, и применили его к решению очень больших инженерных сооружений, подвергающихся динамической нагрузке. [2] Это было достигнуто с использованием метода очистки векторов Ланцоша (то есть путем многократной реортогонализации каждого вновь созданного вектора со всеми ранее созданными) [2] с любой степенью точности, которая, если не выполнялась, давала серию векторов, которые были сильно загрязнены теми, которые связаны с самыми низкими собственными частотами.
В своей первоначальной работе эти авторы также предложили, как выбрать начальный вектор (т. Е. Использовать генератор случайных чисел для выбора каждого элемента начального вектора), и предложили эмпирически определенный метод определения , уменьшенное количество векторов (т. е. оно должно быть выбрано примерно в 1,5 раза больше желаемого точного количества собственных значений). Вскоре после этого за их работой последовала Пейдж, которая также представила анализ ошибок. [3] [4] В 1988 году Оялво представил более подробную историю этого алгоритма и эффективный тест на ошибку собственных значений. [5]
Алгоритм
- Входная эрмитова матрица размера , и, возможно, несколько итераций (по умолчанию пусть ).
- Строго говоря, алгоритму не нужен доступ к явной матрице, а только функция который вычисляет произведение матрицы на произвольный вектор. Эта функция вызывается не более чем раз.
- Выход матрица с ортонормированными столбцами и трехдиагональной вещественной симметричной матрицей размера . Если , тогда является унитарным , и .
- Предупреждение Итерация Ланцоша подвержена численной нестабильности. При выполнении неточной арифметики необходимо принять дополнительные меры (как описано в следующих разделах) для обеспечения достоверности результатов.
- Позволять - произвольный вектор с евклидовой нормой .
- Сокращенный этап начальной итерации:
- Позволять .
- Позволять .
- Позволять .
- Для делать:
- Позволять (также евклидова норма ).
- Если , тогда пусть ,
- иначе выберите как произвольный вектор с евклидовой нормой который ортогонален всем .
- Позволять .
- Позволять .
- Позволять .
- Позволять матрица со столбцами . Позволять.
- Примечание для .
В принципе, существует четыре способа написать итерационную процедуру. Пейдж и другие работы показывают, что вышеуказанный порядок операций является наиболее численно устойчивым. [6] [7] На практике начальный вектор можно рассматривать как еще один аргумент процедуры, с и индикаторы числовой неточности, включенные в качестве дополнительных условий завершения цикла.
Не считая умножения матрицы на вектор, каждая итерация делает арифметические операции. Умножение матрицы на вектор может быть выполнено в арифметические операции, где - среднее количество ненулевых элементов в строке. Таким образом, общая сложность, или же если ; алгоритм Ланцоша может быть очень быстрым для разреженных матриц. Схемы для улучшения числовой стабильности обычно оцениваются по этой высокой производительности.
Векторы называются векторами Ланцоша . Вектор не используется после вычисляется, а вектор не используется после вычисляется. Следовательно, можно использовать одно и то же хранилище для всех трех. Аналогично, если только трехдиагональная матрица ищется, то необработанная итерация не требуется после вычисления , хотя для некоторых схем повышения численной устойчивости он понадобится в дальнейшем. Иногда последующие векторы Ланцоша пересчитываются из при необходимости.
Приложение к проблеме собственных значений
Алгоритм Ланцоша чаще всего упоминается в контексте поиска собственных значений и собственных векторов матрицы, но в то время как обычная диагонализация матрицы сделала бы собственные векторы и собственные значения очевидными при проверке, то же самое нельзя сказать о трехдиагонализации, выполненной методом Ланцоша. алгоритм; Для вычисления даже одного собственного значения или собственного вектора необходимы нетривиальные дополнительные шаги. Тем не менее, применение алгоритма Ланцоша часто является значительным шагом вперед в вычислении собственного разложения. Если является собственным значением , и если ( является собственным вектором ) тогда - соответствующий собственный вектор (поскольку ). Таким образом, алгоритм Ланцоша преобразует задачу собственного разложения для в задачу собственного разложения для .
- Для трехдиагональных матриц существует ряд специализированных алгоритмов, часто с большей вычислительной сложностью, чем алгоритмы общего назначения. Например, если является трехдиагональная симметричная матрица, тогда:
- Фрикативный рекурсии позволяет вычисления характеристического полинома ин операций, и оценивая его в момент операции.
- Разделяй и властвуй собственное алгоритм может быть использован для вычисления всего eigendecomposition из в операции.
- Метод Fast Multipole Method [8] позволяет вычислить все собственные значения всего за операции.
- Известно, что некоторые общие алгоритмы разложения на собственные числа, в частности алгоритм QR , сходятся быстрее для трехдиагональных матриц, чем для общих матриц. Асимптотическая сложность трехдиагонального QR равнатак же, как для алгоритма «разделяй и властвуй» (хотя постоянный множитель может быть другим); так как собственные векторы вместе имеют элементов, это асимптотически оптимально.
- Даже алгоритмы, скорость сходимости которых не зависит от унитарных преобразований, таких как степенной метод и обратная итерация , могут обладать низкими преимуществами производительности от применения к трехдиагональной матрице. а не исходная матрица . Сочень разреженный, со всеми ненулевыми элементами в хорошо предсказуемых позициях, он обеспечивает компактное хранение с превосходной производительностью по сравнению с кэшированием . Так же,является вещественной матрицей со всеми собственными векторами и собственными значениями действительными, тогда как в общем случае может иметь комплексные элементы и собственные векторы, поэтому вещественной арифметики достаточно для нахождения собственных векторов и собственных значений .
- Если очень большой, то уменьшение чтобы имеет управляемый размер, но все же позволит находить более экстремальные собственные значения и собственные векторы ; вВ этой области алгоритм Ланцоша можно рассматривать как схему сжатия с потерями для эрмитовых матриц, которая подчеркивает сохранение крайних собственных значений.
Сочетание хорошей производительности для разреженных матриц и способности вычислять несколько (без вычисления всех) собственных значений являются основными причинами использования алгоритма Ланцоша.
Применение к тридиагонализации
Хотя проблема собственных значений часто является мотивацией для применения алгоритма Ланцоша, операция, которую в первую очередь выполняет алгоритм, - это трехдиагонализация матрицы, для которой численно стабильные преобразования Хаусхолдера предпочитаются с 1950-х годов. В 1960-е годы алгоритм Ланцоша не принимался во внимание. Интерес к нему был возрожден теорией сходимости Каниэля – Пейджа и разработкой методов предотвращения числовой нестабильности, но алгоритм Ланцоша остается альтернативным алгоритмом, который можно попробовать только в том случае, если Хаусхолдер не удовлетворителен. [9]
Аспекты, в которых различаются два алгоритма, включают:
- Ланцош пользуется преимуществами будучи разреженной матрицей, тогда как Householder этого не делает и будет генерировать заполнение .
- Ланцош полностью работает с исходной матрицей. (и не имеет проблем с тем, что он известен только неявно), тогда как необработанный Хаусхолдер хочет изменить матрицу во время вычисления (хотя этого можно избежать).
- Каждая итерация алгоритма Ланцоша создает еще один столбец окончательной матрицы преобразования. , тогда как итерация Хаусхолдера дает еще один фактор в унитарной факторизации из . Однако каждый фактор определяется одним вектором, поэтому требования к хранилищу одинаковы для обоих алгоритмов, и можно вычислить в время.
- Домохозяин численно стабилен, в то время как сырой Ланцош - нет.
- Ланцош очень параллелен, только точки синхронизации (расчеты а также ). Домохозяин менее параллелен, имея последовательность вычислены скалярные величины, каждая из которых зависит от предыдущей величины в последовательности.
Вывод алгоритма
Есть несколько аргументов, которые приводят к алгоритму Ланцоша.
Более предусмотрительный метод силы
Степенной метод нахождения наибольшего собственного значения и соответствующего собственного вектора матрицы примерно
- Выберите случайный вектор .
- Для (до направления сошлась) делать:
- Позволять
- Позволять
- В большом предел приближается к нормированному собственному вектору, соответствующему самому большому собственному значению модуля.
Критика, которая может быть высказана против этого метода, заключается в том, что он расточителен: он тратит много работы (произведение матрица-вектор на шаге 2.1) на извлечение информации из матрицы , но обращает внимание только на самый последний результат; реализации обычно используют одну и ту же переменную для всех векторов, при которой каждая новая итерация перезаписывает результаты предыдущей. Что, если вместо этого мы сохраним все промежуточные результаты и систематизируем их данные?
Одна часть информации, которую легко получить из векторов является цепочкой подпространств Крылова . Один из способов заявить, что, не вводя наборы в алгоритм, - это заявить, что он вычисляет
- подмножество основы такой, что для каждого и все
это тривиально удовлетворяется так долго как линейно не зависит от (а в случае наличия такой зависимости можно продолжить последовательность, выбрав произвольный вектор, линейно независимый от ). Основа, содержащаявекторы, однако, вероятно, будут численно плохо обусловлены , так как эта последовательность векторов предназначается, чтобы сходиться к собственному вектору. Чтобы избежать этого, можно объединить степенную итерацию с процессом Грама – Шмидта , чтобы вместо этого получить ортонормированный базис этих подпространств Крылова.
- Выберите случайный вектор евклидовой нормы . Позволять.
- Для делать:
- Позволять .
- Для всех позволять . (Это координаты относительно базисных векторов .)
- Позволять . (Отмените компонент это в .)
- Если тогда пусть а также ,
- в противном случае выберите как произвольный вектор евклидовой нормы который ортогонален всем .
Связь между векторами степенных итераций и ортогональные векторы в том, что
- .
Здесь можно заметить, что на самом деле нам не нужен векторов для вычисления этих , так как и поэтому разница между а также в , который компенсируется процессом ортогонализации. Таким образом, тот же базис для цепочки подпространств Крылова вычисляется с помощью
- Выберите случайный вектор евклидовой нормы .
- Для делать:
- Позволять .
- Для всех позволять .
- Позволять .
- Позволять .
- Если тогда пусть ,
- в противном случае выберите как произвольный вектор евклидовой нормы который ортогонален всем .
Априори коэффициенты удовлетворить
- для всех ;
Определение может показаться немного странным, но соответствует общей схеме поскольку
Поскольку векторы степенной итерации которые были исключены из этой рекурсии, удовлетворяют векторы и коэффициенты содержать достаточно информации из что все можно вычислить, поэтому при переключении векторов ничего не потеряно. (Действительно, оказывается, что собранные здесь данные дают значительно лучшие приближения к наибольшему собственному значению, чем можно получить от равного числа итераций в степенном методе, хотя на данный момент это не обязательно очевидно.)
Эта последняя процедура - итерация Арнольди . Алгоритм Ланцоша возникает как упрощение, получаемое от исключения шагов вычисления, которые оказываются тривиальными, когда является эрмитовым - в частности, большинство коэффициенты оказываются равными нулю.
Элементарно, если эрмитово тогда
Для мы знаем это , и с тех пор по построению ортогонален этому подпространству, это внутреннее произведение должно быть нулевым. (По сути, это также причина того, почему последовательности ортогональных многочленов всегда могут быть заданы трехчленным рекуррентным соотношением .) один получает
поскольку последний реален в силу того, что является нормой вектора. Для один получает
это значит, что это тоже реально.
Более абстрактно, если матрица со столбцами тогда числа можно идентифицировать как элементы матрицы , а также для матрица является верхней хессенбергова . С
матрица эрмитово. Это означает, чтотакже является более низким по Гессенбергу, поэтому на самом деле он должен быть трехъядерным. Поскольку его главная диагональ является эрмитовой, она действительна, и поскольку ее первая поддиагональ реальна по построению, то же самое верно и для ее первой наддиагонали. Следовательно, является действительной симметричной матрицей - матрицей спецификации алгоритма Ланцоша.
Одновременное приближение крайних собственных значений
Один из способов охарактеризовать собственные векторы эрмитовой матрицы как стационарные точки в частном Рэлеи
В частности, наибольшее собственное значение это глобальный максимум и наименьшее собственное значение это глобальный минимум .
В подпространстве малой размерности из возможно найти максимальное и минимум из . Повторяя это для возрастающей цепочки производит две последовательности векторов: а также такой, что а также
Тогда возникает вопрос, как выбрать подпространства, чтобы эти последовательности сходились с оптимальной скоростью.
Из , оптимальное направление поиска больших значений это градиент , а также от оптимальное направление поиска меньших значений это отрицательный градиент . В общем
так что интересующие направления достаточно легко вычислить в матричной арифметике, но если кто-то хочет улучшить оба а также Затем следует принять во внимание два новых направления: а также поскольку а также могут быть линейно независимыми векторами (действительно, близкими к ортогональным), в общем случае нельзя ожидать а также быть параллельным. Следовательно, необходимо ли увеличивать размер от на каждом шагу? Нет, если считаются подпространствами Крылова, потому что тогда для всех таким образом, в частности, для обоих а также .
Другими словами, мы можем начать с некоторого произвольного начального вектора построить векторные пространства
а затем искать такой, что
Поскольку th power метод итерации принадлежит из этого следует, что итерация для получения а также не может сходиться медленнее, чем в степенном методе, и добьется большего, аппроксимируя оба крайних значения собственных значений. Для подзадачи оптимизации на некоторых , удобно иметь ортонормированный базис для этого векторного пространства. Таким образом, мы снова приходим к проблеме итеративного вычисления такого базиса для последовательности подпространств Крылова.
Конвергенция и другая динамика
При анализе динамики алгоритма удобно брать собственные значения и собственные векторы как указано, даже если они явно не известны пользователю. Чтобы зафиксировать обозначения, пусть быть собственными числами (все они, как известно, действительны, и поэтому их можно упорядочить), и пусть - ортонормированный набор собственных векторов такой, что для всех .
Также удобно зафиксировать обозначения для коэффициентов исходного вектора Ланцоша относительно этого собственного базиса; позволять для всех , чтобы . Начальный векторисчерпание некоторого собственного значения приведет к задержке сходимости к соответствующему собственному значению, и даже несмотря на то, что это просто является постоянным множителем в границах ошибки, истощение остается нежелательным. Один из распространенных методов, позволяющих избежать постоянных ударов, - это выбратьсначала отрисовывая элементы случайным образом в соответствии с тем же нормальным распределением со средним значением а затем масштабируйте вектор до нормы . Перед изменением масштаба это приводит к тому, что коэффициенты также быть независимыми нормально распределенными стохастическими переменными из того же нормального распределения (поскольку изменение координат унитарно), и после масштабирования вектора будет иметь равномерное распределение на единичной сфере в. Это позволяет ограничить вероятность того, что, например,.
Тот факт, что алгоритм Ланцоша не зависит от координат - операции смотрят только на внутренние произведения векторов, а не на отдельные элементы векторов, - позволяет легко создавать примеры с известной собственной структурой для запуска алгоритма: make диагональная матрица с искомыми собственными значениями на диагонали; пока начальный вектор имеет достаточно ненулевых элементов, алгоритм выдаст общую трехдиагональную симметричную матрицу как .
Теория сходимости Кэниела – Пейджа
После итерационные шаги алгоритма Ланцоша, является вещественная симметричная матрица, имеющая аналогично предыдущему собственные значения Под сходимостью в первую очередь понимается сходимость к (и симметричная сходимость к ) в виде растет, и во вторую очередь сближение некоторого диапазона собственных значений своим коллегам из . Сходимость для алгоритма Ланцоша часто на порядки быстрее, чем для алгоритма степенной итерации. [9] : 477
Границы для исходят из приведенной выше интерпретации собственных значений как крайних значений фактора Рэлея . С является априори максимумом в целом тогда как это просто максимум на -мерное подпространство Крылова, тривиально получаем . И наоборот, любая точка в этом подпространстве Крылова оценивается снизу для , так что если можно выставить точку, за которую мала, то это обеспечивает жесткую границу .
Измерение Крылова подпространство
так что любой его элемент может быть выражен как для некоторого полинома степени не более ; коэффициенты этого многочлена - это просто коэффициенты линейной комбинации векторов. У желаемого многочлена окажутся действительные коэффициенты, но на данный момент мы должны учитывать также и комплексные коэффициенты, и мы напишем для полинома, полученного комплексным сопряжением всех коэффициентов . В этой параметризации подпространства Крылова имеем
Используя теперь выражение для как линейную комбинацию собственных векторов, получаем
и в более общем плане
для любого полинома .
Таким образом
Ключевое различие между числителем и знаменателем здесь заключается в том, что член исчезает в числителе, но не в знаменателе. Таким образом, если можно выбрать быть большим в но мал во всех остальных собственных значениях, можно получить жесткую границу ошибки .
С имеет гораздо больше собственных значений, чем имеет коэффициенты, это может показаться сложной задачей, но один из способов добиться этого - использовать многочлены Чебышева . Письмо на степень Полином Чебышева первого рода (удовлетворяющий для всех ), у нас есть многочлен, который остается в диапазоне на известном интервале но быстро растет вне его. При некотором масштабировании аргумента мы можем отобразить все собственные значения, кроме в . Позволять
(в случае , используйте вместо этого наибольшее собственное значение, строго меньшее, чем ), то максимальное значение для является а минимальное значение равно , так
более того
количество
(то есть отношение первой собственной щели к диаметру остальной части спектра ), таким образом, имеет ключевое значение для скорости сходимости здесь. Также пишу
мы можем сделать вывод, что
Таким образом, скорость сходимости контролируется главным образом , поскольку эта граница уменьшается в раз за каждую дополнительную итерацию.
Для сравнения можно рассмотреть, как скорость сходимости степенного метода зависит от , но поскольку степенной метод в первую очередь чувствителен к отношению между абсолютными значениями собственных значений, нам нужно для собственного зазора между а также быть доминирующим. При этом ограничении наиболее благоприятным для степенного метода является то, что, так что считайте это. В конце метода мощности вектор итерации:
- [примечание 1]
где каждая новая итерация эффективно умножает -амплитуда от
Тогда оценка наибольшего собственного значения имеет вид
поэтому приведенную выше оценку скорости сходимости алгоритма Ланцоша следует сравнить с
который сжимается в раз для каждой итерации. Таким образом, разница сводится к тому, что между а также . в регион, последний больше похож на , и работает так же, как и силовой метод, с вдвое большей собственной щелью; заметное улучшение. Однако более сложным является случай в котором является еще большим улучшением собственной щели; вобласть, в которой алгоритм Ланцоша с точки зрения сходимости дает наименьшее улучшение по сравнению с методом мощности.
Численная стабильность
Стабильность означает, насколько сильно будет затронут алгоритм (то есть будет ли он давать приблизительный результат, близкий к исходному), если будут внесены и накоплены небольшие числовые ошибки. Числовая стабильность является центральным критерием оценки полезности реализации алгоритма на компьютере с округлением.
Для алгоритма Ланцоша можно доказать, что с помощью точной арифметики набор векторовстроит ортонормированный базис, и решаемые собственные значения / векторы являются хорошими приближениями к значениям исходной матрицы. Однако на практике (поскольку вычисления выполняются в арифметике с плавающей запятой, где погрешность неизбежна) ортогональность быстро теряется, и в некоторых случаях новый вектор может даже линейно зависеть от уже построенного набора. В результате некоторые из собственных значений результирующей трехдиагональной матрицы могут не быть приближениями к исходной матрице. Следовательно, алгоритм Ланцоша не очень стабилен.
Пользователи этого алгоритма должны иметь возможность находить и удалять эти «ложные» собственные значения. Практические реализации алгоритма Ланцоша идут в трех направлениях для борьбы с этой проблемой стабильности: [6] [7]
- Предотвратить потерю ортогональности,
- Восстановите ортогональность после создания основы.
- После определения хороших и «ложных» собственных значений удалите ложные.
Вариации
Существуют вариации алгоритма Ланцоша, где задействованные векторы представляют собой высокие узкие матрицы вместо векторов, а нормализующие константы представляют собой небольшие квадратные матрицы. Они называются «блочными» алгоритмами Ланцоша и могут быть намного быстрее на компьютерах с большим количеством регистров и длительным временем выборки из памяти.
Многие реализации алгоритма Ланцоша перезапускаются после определенного количества итераций. Одним из наиболее важных вариантов перезапуска является неявно перезапускаемый метод Ланцоша [10], который реализован в ARPACK . [11] Это привело к ряду других перезапущенных вариаций, таких как перезапуск бидиагонализации Ланцоша. [12] Другой успешный вариант перезапуска - это метод Ланцоша с толстым перезапуском [13], который был реализован в программном пакете под названием TRLan. [14]
Нулевое пространство над конечным полем
В 1995 году Питер Монтгомери опубликовал алгоритм, основанный на алгоритме Ланцоша, для поиска элементов нулевого пространства большой разреженной матрицы над GF (2) ; поскольку множество людей, интересующихся большими разреженными матрицами над конечными полями, и множество людей, интересующихся большими проблемами собственных значений, практически не пересекаются, это часто также называют блочным алгоритмом Ланцоша, не вызывая необоснованной путаницы. [ необходима цитата ]
Приложения
Алгоритмы Ланцоша очень привлекательны тем, что умножение на единственная крупномасштабная линейная операция. Поскольку механизмы поиска текста с взвешенными терминами реализуют именно эту операцию, алгоритм Ланцоша может эффективно применяться к текстовым документам (см. Скрытое семантическое индексирование ). Собственные векторы также важны для крупномасштабных методов ранжирования, таких как алгоритм HITS, разработанный Джоном Кляйнбергом , или алгоритм PageRank , используемый Google.
Ланцош алгоритмы также используются в физике конденсированной сред в качестве способа для решения гамильтонианов из сильно коррелированных электронных систем , [15] , а также в оболочке модель коды в ядерной физике . [16]
Реализации
NAG библиотека содержит несколько подпрограмм [17] для решения крупномасштабных линейных систем и собственных значений , которые используют алгоритм Ланцоша.
MATLAB и GNU Octave поставляются со встроенным ARPACK. Как хранимые, так и неявные матрицы можно анализировать с помощью функции eigs () ( Matlab / Octave ).
Реализация алгоритма Ланцоша в Matlab (проблемы с точностью заметок) доступна как часть пакета Matlab для распространения веры по Гауссу . GraphLab [18] совместная библиотека фильтрации включает в себя большую реализацию шкалы параллели Lanczos алгоритм (в C ++) для многоядерного.
Библиотека PRIMME также реализует алгоритм, подобный Ланцошу .
Заметки
- ^ Коэффициенты не обязательно должны быть действительными, но фаза не имеет большого значения. Не обязательно, чтобы составные части для других собственных векторов полностью исчезли, но они сокращаются по крайней мере так же быстро, как и для других собственных векторов., так описывает худший случай.
Рекомендации
- ^ Ланцош, С. (1950). «Итерационный метод решения проблемы собственных значений линейных дифференциальных и интегральных операторов» (PDF) . Журнал исследований Национального бюро стандартов . 45 (4): 255–282. DOI : 10,6028 / jres.045.026 .
- ^ а б Оялво, IU; Ньюман, М. (1970). «Режимы вибрации крупногабаритных конструкций методом автоматического уменьшения матрицы». Журнал AIAA . 8 (7): 1234–1239. Bibcode : 1970AIAAJ ... 8.1234N . DOI : 10.2514 / 3.5878 .
- ^ Пейдж, CC (1971). Вычисление собственных значений и собственных векторов очень больших разреженных матриц (кандидатская диссертация). Лондонский университет. OCLC 654214109 .
- ^ Пейдж, CC (1972). "Вычислительные варианты метода Ланцоша для задачи собственных значений". J. Inst. Maths Applics . 10 (3): 373–381. DOI : 10.1093 / имамата / 10.3.373 .
- ^ Оялво, И.Ю. (1988). «Происхождение и преимущества векторов Ланцоша для больших динамических систем». Proc. 6-я Конференция по модальному анализу (IMAC), Киссимми, Флорида . С. 489–494.
- ^ а б Cullum; Уиллоби. Алгоритмы Ланцоша для вычисления больших симметричных собственных значений . 1 . ISBN 0-8176-3058-9.
- ^ а б Юсеф Саад (1992-06-22). Численные методы для больших задач на собственные значения . ISBN 0-470-21820-7.
- ^ Coakley, Ed S .; Рохлин, Владимир (2013). «Быстрый алгоритм« разделяй и властвуй »для вычисления спектров реальных симметричных трехдиагональных матриц» . Прикладной и вычислительный гармонический анализ . 34 (3): 379–414. DOI : 10.1016 / j.acha.2012.06.003 .
- ^ а б Golub, Gene H .; Ван Лоан, Чарльз Ф. (1996). Матричные вычисления (3-е изд.). Балтимор: Johns Hopkins Univ. Нажмите. ISBN 0-8018-5413-X.
- ^ Д. Кальветти ; Л. Райхель; DC Соренсен (1994). "Неявно перезапущенный метод Ланцоша для больших симметричных задач на собственные значения" . Электронные транзакции по численному анализу . 2 : 1–21.
- ^ РБ Лехук; DC Соренсен; К. Ян (1998). Руководство пользователя ARPACK: Решение крупномасштабных проблем собственных значений с помощью неявно перезапущенных методов Арнольди . СИАМ. DOI : 10.1137 / 1.9780898719628 . ISBN 978-0-89871-407-4.
- ^ Э. Кокиопулу; К. Бекас; Э. Галлопулос (2004). «Вычисление наименьших сингулярных троек с неявно перезапущенной бидиагонализацией Ланцоша» (PDF) . Прил. Нумер. Математика . 49 : 39–61. DOI : 10.1016 / j.apnum.2003.11.011 .
- ^ Кешенг Ву; Хорст Саймон (2000). "Толстый перезапуск метода Ланцоша для больших симметричных задач на собственные значения" . Журнал SIAM по матричному анализу и приложениям . СИАМ. 22 (2): 602–616. DOI : 10.1137 / S0895479898334605 .
- ^ Кешенг Ву; Хорст Саймон (2001). «Программный комплекс TRLan» . Архивировано из оригинала на 2007-07-01 . Проверено 30 июня 2007 .
- ^ Чен, HY; Аткинсон, Вашингтон; Уортис, Р. (июль 2011 г.). "Вызванная беспорядком аномалия нулевого смещения в модели Андерсона-Хаббарда: численные и аналитические расчеты". Physical Review B . 84 (4): 045113. arXiv : 1012.1031 . Bibcode : 2011PhRvB..84d5113C . DOI : 10.1103 / PhysRevB.84.045113 .
- ^ Симидзу, Норитака (21 октября 2013 г.). «Код модели ядерной оболочки для массовых параллельных вычислений,« КШЕЛЛ » ». Arxiv : 1310.5431 [ Nucl-й ].
- ^ Группа численных алгоритмов. "Указатель ключевых слов: Ланцош" . Руководство библиотеки NAG, Марк 23 . Проверено 9 февраля 2012 .
- ^ GraphLab Архивировано 14 марта 2011 г. на Wayback Machine
дальнейшее чтение
- Голуб, Джин Х .; Ван Лоан, Чарльз Ф. (1996). «Методы Ланцоша» . Матричные вычисления . Балтимор: Издательство Университета Джона Хопкинса. С. 470–507. ISBN 0-8018-5414-8.
- Нг, Эндрю Ю .; Чжэн, Алиса X .; Джордан, Майкл И. (2001). "Анализ связи, собственные векторы и стабильность" (PDF) . IJCAI'01 Труды 17-й Международной совместной конференции по искусственному интеллекту . 2 : 903–910.