EISPACK

EISPACK — это пакет программ для решения задач на собственные значения и собственные векторы матриц, разработанный в 1970-х годах в Национальной лаборатории Аргонны (США). EISPACK является одним из первых в мире специализированных библиотек численного линейного алгебраического программного обеспечения, наряду с LINPACK (для решения систем линейных уравнений) и LAPACK (более поздняя, универсальная библиотека). Пакет написан на языке Фортран и предназначен для использования на мейнфреймах и суперкомпьютерах того времени.

История

Разработка EISPACK началась в 1971 году под руководством Б. С. Гарбова, Дж. М. Бойла, Дж. Дж. Донгарры и К. К. Моллера. Проект финансировался Национальным научным фондом США и Министерством энергетики США. Основной целью было создание надежного, переносимого и хорошо документированного набора подпрограмм для решения задач на собственные значения, которые были критически важны для многих научных и инженерных приложений — от квантовой химии до структурной механики.

Первая версия пакета (EISPACK-1) была выпущена в 1972 году. Она включала около 30 подпрограмм, реализующих методы Якоби, QR-алгоритм, метод обратных итераций и другие алгоритмы для вещественных и комплексных матриц общего вида, а также для симметричных и эрмитовых матриц. В 1973 году вышла версия EISPACK-2, расширенная для работы с матрицами в ленточном и разреженном представлениях. В 1976 году был опубликован пакет EISPACK-3, который включал подпрограммы для решения обобщенных задач на собственные значения (Ax = λB*x).

Распространение EISPACK осуществлялось через библиотеку Netlib, а также в составе математических пакетов, таких как IMSL и NAG. Пакет стал стандартом де-факто для вычисления собственных значений в научных расчетах на протяжении 1970-х и 1980-х годов.

Классификация подпрограмм

Подпрограммы EISPACK классифицируются по типу решаемой задачи и структуре матрицы.

По типу задачи

• Стандартная задача на собственные значения: Ax = λx, где A — квадратная матрица, λ — собственное значение, x — собственный вектор.
• Обобщенная задача на собственные значения: Ax = λB*x, где A и B — квадратные матрицы, B — обычно положительно определённая или симметричная.

По структуре матрицы

• Полные матрицы общего вида: вещественные или комплексные, без специальной структуры.
• Симметричные и эрмитовы матрицы: A = A^T (вещественные) или A = A* (комплексные). Для них используются более эффективные и устойчивые алгоритмы.
• Ленточные матрицы: ненулевые элементы сосредоточены вблизи главной диагонали.
• Разреженные матрицы: матрицы с большим числом нулевых элементов, для которых применяются итерационные методы.

Устройство и алгоритмы

EISPACK реализует несколько ключевых алгоритмов численной линейной алгебры.

QR-алгоритм

Основной алгоритм для вычисления всех собственных значений вещественных или комплексных матриц общего вида. Матрица сначала приводится к верхней форме Хессенберга (почти треугольной) с помощью преобразований Хаусхолдера, а затем к верхней треугольной форме с помощью итераций QR-разложения. Для симметричных матриц применяется его симметричный вариант — алгоритм QL.

Метод Якоби

Итерационный метод для симметричных матриц, основанный на последовательном обнулении внедиагональных элементов с помощью вращений Гивенса. Обеспечивает высокую точность, но медленнее QR-алгоритма для больших матриц.

Метод обратных итераций

Используется для вычисления собственных векторов после того, как собственные значения найдены. Метод основан на решении системы линейных уравнений (A - λI)*x = b с последующей нормировкой и итерацией.

Метод бисекции

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

Метод Ланцоша

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

Применение

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

• Квантовая химия: решение уравнения Шрёдингера для молекул и кристаллов методом Хартри — Фока, где задача сводится к обобщённой задаче на собственные значения.
• Структурная механика: анализ устойчивости и собственных колебаний конструкций (мостов, зданий, самолётов), где матрицы жёсткости и масс являются симметричными и ленточными.
• Гидродинамика и аэродинамика: анализ устойчивости течений жидкости и газа, где задача сводится к решению задачи на собственные значения для оператора Навье — Стокса.
• Обработка сигналов: методы MUSIC и ESPRIT для оценки частотных составляющих сигналов, основанные на разложении ковариационной матрицы.
• Машинное обучение: метод главных компонент (PCA) и спектральная кластеризация, где собственные векторы ковариационной матрицы используются для снижения размерности и выделения признаков.

Влияние и наследие

EISPACK стал основой для многих последующих разработок в области численной линейной алгебры. Его подпрограммы были включены в состав библиотек IMSL и NAG, а также в ранние версии MATLAB, где они использовались для реализации функций eig() и svd(). В 1990-х годах EISPACK был заменён более современной библиотекой LAPACK, которая объединила и расширила функциональность EISPACK и LINPACK, используя блочные алгоритмы для эффективной работы на векторных и параллельных вычислительных системах. Тем не менее, многие алгоритмы, разработанные в рамках проекта EISPACK, остаются актуальными и используются в современных численных пакетах (например, в SciPy, NumPy, Julia).

Критика

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

Источники

• Garbow, B. S., Boyle, J. M., Dongarra, J. J., & Moler, C. B. (1972). Matrix Eigensystem Routines — EISPACK Guide. Springer-Verlag.
• Smith, B. T., Boyle, J. M., Dongarra, J. J., Garbow, B. S., Ikebe, Y., Klema, V. C., & Moler, C. B. (1976). Matrix Eigensystem Routines — EISPACK Guide Extension. Springer-Verlag.
• Dongarra, J. J., & Walker, D. W. (1995). Software Libraries for Linear Algebra Computations on High Performance Computers. SIAM Review, 37(2), 151–180.
• Wilkinson, J. H., & Reinsch, C. (1971). Handbook for Automatic Computation, Volume II: Linear Algebra. Springer-Verlag.