Алгебраические структуры и параллельные вычисления в задачах квантовой химии тема диссертации и автореферата по ВАК РФ 05.13.16, кандидат физико-математических наук Ибрагимов, Ильгиз Владимирович

• Ибрагимов, Ильгиз Владимирович
• кандидат физико-математических наук
• 1998

Оглавление диссертации кандидат физико-математических наук Ибрагимов, Ильгиз Владимирович

Содержание

Введение

1 Задачи и методы нахождения электронного строения молекул

1.1 Постановки химических задач

1.2 Вычислительные методы нахождения электронного строения молекул

1.3 Метод Фока решения многоэлектронного уравнения Шре-дингера в одноконфигурационном приближении

1.4 Условие минимума энергии

1.5 Условие единственности минимума энергии

1.6 Численное решение уравнений Хартри-Фока

1.6.1 Метод теории возмущений для решения уравнений Хартри-Фока

1.6.2 Метод тестовых функций для решения уравнений Хартри-Фока

1.7 Актуальные проблемы

2 Базисы на основе регулярных конечных элементов

2.1 Вычисление интегралов

2.2 Свойства дискретизованного функционала Хартри-Фока 54 2.2.1 Вычисление значения дискретизованного функционала энергии Хартри-Фока

2.2.2 Вычисление первых производных дискретизован-ного функционала энергии Хартри-Фока

2.2.3 Вычисление вторых производных дискретизован-ного функционала энергии Хартри-Фока

2.2.4 О точных преобразованиях дискретизованного функционала энергии Хартри-Фока

2.2.5 Приближенное вычисление значения дискретизованного функционала энергии Хартри-Фока

2.3 Решение итерационными методами дискретных уравнений Хартри-Фока

2.4 Построение предобуславливателей для метода Давидсона

2.4.1 Метод решения систем линейных уравнений с матрицей вида М + И

2.4.2 Аппроксимация задачи С + И задачей М. + И

3 Численные эксперименты

4 Принципы распараллеливания программного комплекса по решению уравнений Хартри-Фока

4.1 Параллельные алгоритмы БПФ и скалярного произведения векторов

4.2 Теоретические исследования параллельных алгоритмов БПФ и вычисления суммы векторов

4.3 Численные эксперименты

4.4 Параллельная реализация программного комплекса по решению уравнений Хартри-Фока

Заключение

Литература

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

Введение

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

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

Для моделирования используются уравнения Хартри-Фока [1]. Решением этих уравнений являются несколько минимальных собственных значений и соответствующих собственных функций некоторого эр-митового оператора.

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

Оператор Хартри-Фока задан в трехмерном пространстве и состоит из суммы трех операторов:

Т — кинетической энергии электронов;

У\ — потенциальной энергии электронов в поле ядер атомов;

V2 — потенциальной энергии электронов в поле, которое создается всеми остальными электронами.

По порядку линейный оператор Т больше двух остальных операторов У\ и V-?.

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

Для решения такой задачи методом дискретизации в этой работе предлагается использовать в качестве базисных функций конечные элементы на регулярной сетке. В этом случае дискретный оператор Хартри-Фока записывается в виде:

I -ь + бе, - - Е с;тсг + ¿(ад (т £ с;сЛ I Сз = О, V; - 1,..., м,

где Ь и 5 — ленточные трехуровневые [2] симметричные матрицы, причем £ может быть единичной; Т — циркулянтная трехуровневая положительно определенная симметричная матрица; С{ — ленточные трехуровневые симметричные матрицы, составленные из элементов г-ого собственного вектора С^; Е^ — ^'-ый собственный вектор и соответствующее ему собственное значение; М — число электронных пар в системе.

Такой подход позволяет применять итерационные методы типа Ланцоша [3] и Давидсона [4] так, что арифметические затраты умножения вектора на дискретный оператор имеют порядок N ./V против ТУ2 для базисных функций неструктурированного вида и Д^4 для базисных функций с бесконечным носителем. Также разработаны эффективные предобуславливатели для такой задачи с тем же порядком арифметической сложности.

В то время, когда были сформулированы эти идеи, было очевидно, что для решения реальных химических проблем необходимо использовать мощные ЭВМ, поэтому второй частью этой работы является разработка эффективных параллельных алгоритмов решения уравнений Хартри-Фока. Оказалось, что для работы алгоритма решения уравнений Хартри-Фока на массивно-параллельном компьютере необходимо три коммуникационных примитива: умножение вектора на ленточную матрицу (а именно трехуровневую трехдиагональную симметричную); операция БПФ с распределенным вектором и операция вычисления скалярного произведения векторов, которые распределены по процессорам.

При разработке этих коммуникационных примитивов была применена модель, в которой время передачи данных между процессорами выражается в виде сг + где а — время задержки для подготовительной работы (измеряется в количестве операций с плавающей точкой, которые можно сделать за время этой задержки), т — скорость передачи (слово/время выполнения одной операции с плавающей точкой), N — число слов в передаваемом пакете. Как оказалось, такая сравнительно простая модель позволяет хорошо описать реально наблюдаемые величины на компьютерах типа МВС-100/1000 [5].

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

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

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

Для двух других коммуникационных примитивов дело обстоит намного сложнее. В зависимости.от того, каковы величины <т и т параллельного компьютера, каков размер задачи (N) и число используемых процессоров (Р), меняется параллельный алгоритм, который при данных параметрах будет более эффективен. Поэтому предлагается следующий подход для нахождения наиболее эффективного алгоритма. Построим класс алгоритмов, которые будут зависеть от одного параметра, причем этот параметр должен, по возможности хорошо описывать все возможные параллельные алгоритмы. Далее в терминах модели а и т выпишем время работы алгоритма в зависимости о этого параметра, и минимизируем время работы алгоритма по этому параметру при заданных сг, г, N и Р. Для операции вычисления скалярного произведения такой подход однажды уже был применен для эффективной реализации этого алгоритма на компьютере CRAY — T3D [5].

Был выписан класс параллельных алгоритмов, зависящих от параметра (допустимые значения этого параметра — целые числа на отрезке [l,log2P]) и реализован на компьютере МВС-100. В результате удалось получить, что эти алгоритмы хорошо масштабируемы для реального числа процессоров.

На основе этих коммуникационных примитивов был разработан комплекс программ по решению уравнений Хартри-Фока. Было получено, что с помощью этого комплекса можно решить очень большие задачи (область 643, число электронных пар до 19, это почти 10 миллионов неизвестных) за реальное время, так как наблюдаемая производительность достигала 70 MFlop/s.

Заключение диссертации по теме «Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях (по отраслям наук)», Ибрагимов, Ильгиз Владимирович

Заключение

Итак, в этой работе получены следующие результаты:

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

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

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

• Написан программный комплекс по решению уравнений Хартри-Фока для однопроцессорного компьютера с использованием дисковой памяти и для массивно-параллельных компьютеров с распределенной памятью и проведены численные эксперименты, которые показали хорошие результаты как по предсказанию свойств веществ, так и по эффективности распараллеливания.

Список литературы диссертационного исследования кандидат физико-математических наук Ибрагимов, Ильгиз Владимирович, 1998 год

Литература

[1] W.J. Herbe, L. Radom, P.v.R. Schleyer, J.A. Pople. Ab initio Molecular orbital theory. Springer-Verlag. (1986), —425p.

[2] В. В. Воеводин. E. E. Тыртышников. Вычислительные процессы с тёплицевыми матрицами. — М.: Наука, (1987), — 316с.

[3] Y. Saad. Numerical Methods for Large Eigenvalue Problems. Manchester Univ. Press, Ser. in Algorithms and Arhitectures for Adv. Sci. Comput., (1994), — 344p.

[4] M. Crouzeix, B. Philippe, and M. Sadkane. The Bavidson Method. // SIAM J. Sci. Сотр., v-15, n-1, (1994), pp. 62-76.

[5] И.В. Ибрагимов. Исследование алгоритмов выполнения глобальных операций на массивно-параллельных компьютерах. / Научная апробация слушателей ВКШ. Под ред. В.М. Репина, Вл.В. Воеводина. — М.: МГУ, (1995), с. 39-54.

[6] Г. Родрига. Параллельные вычисления. Пер. с англ. — М.: Наука, (1986), 376 с.

[7] Дж. Марч. Органическая химия. Пер. с англ. — М.: Мир. т. 1-4, (1988).

[8] JI. Д. Ландау, Е. М. Лившиц. Квантовая механика (нерелятивистская теория). — М.: Физматгиз, (1963), — 704с.

[9] А. Н. Верещагин, В. Е. Катаев, А. А. Бредихин, и др. Конформа-ционный анализ углеводородов и их производных. — М.: Наука, (1990), — 296с.

[10] В. М. Татевский. Строение и физико-химические свойства молекул и веществ. — М.: Изд-во МГУ, (1993), — 464с.

[11] JI. Шифф. Квантовая механика: Пер. с англ. — М.: Ин. лит., (1959), — 473с.

[12] К. Накамото. ИК-спектры и спектры КР неорганических и координационных соединений: Пер. с англ. --- М.: Мир, (1991), — 536с.

[13] Местечкин. M. М. Нестабильность уравнений Хартри-Фока и устойчивость молекул. Киев: Наук, думка, (1986), — 176с.

[14] Н. Fukutome. Unrestricted Hartree-Fock theory and its applications to molecules and chemical reactions. // Int. J. Quant. Chem., v-20, n-6, (1981), pp. 955-1065.

[15] J. L. Egido, J. Lessing, V. Martin, L. M. Robledo. On the solution of the Hartree-Fock-Вogoliubov equations by the conjugate gradient method. Nucl. Phys. A.: v-594, (1995), pp. 70-86.

[16] A. P. Seitsonen, M. J. Puska, and R. M. Neiminen. Real-space electronic-structure calculations: Combination of the finite-difference and conjugate gradient methods. Phys. Rev. В.: v-51, n-20, (1995), pp. 14057-14061.

[17] M. C. Payne, M. P. Teter, D. C. Allan, T. A. Arias, and J. D. Joannopoulos. Iterative minimization techniques for ab initio total-energy calculations: molecular dynamics and conjugate gradients. Rev. of Mod. Phys. v-64, n-4, (1992), pp. 1045-1097.

[18] Г. Стренг, Дж. Фикс. Теория метода конечных элементов: Пер. с англ. — М.: Мир, (1977), — 349с.

[19] D. Н. Sleeman. The Determination of SCF LCAO solutions for open shell configurations. Theor. Chim. acta, v-11, n-1, (1968), pp. 135-141.

[20] M. Harvey, A. S. Jensen. The anatomy of the Hartree-Fock procedure in a simple model. Nucl. Phys. A.: v-164, n-5, (1971), pp. 641-657.

[21] J. Koutecky, V. Bonacic. On convergence difficultés in the iterative Hartree-Fock procedure. J. Chem. Phys. v-55, n-5, (1971), pp. 24082413.

[22] S. Ehrenson. Comparisons of the Hûchel and Pariser-Parr-Pople type MO methods. Theor. Chim. acta, v-5, n-4, (1981), pp. 346-368.

[23] R. E. Stenton. Multiple solutions of the Hartree-Fock probleme. 1. General treatment of two-electron closed-shell systems. J. Chem. Phys. v-48, n-1, (1968), pp. 257-262.

[24] A. S. Umar, M. R. Strayer,. J.-S. Wu, D. J. Dean, and M. C. Giiclii. Nuclear Hartree-Fock calculations with splines. Phys. Rev. C.: v-44, n-6, (1991), pp. 2512-2521.

[25] D. M. Charutz, S. Ron, E. Eisenberg, M. Baer. Application of Toeplitz matrices to scattering processes. A NIP-Toeplitz approach to treating chemical reactions. Chem. Phys. Lett, v-244, (1995), pp. 299-304.

[26] J. C. Morrison, Ch. Baunach, L. Larson, B. Bialecki, and G. Fairwaether. Spline collocation calculation for H2 ■ J. Phys. В.: v-29, (1996), pp. 2375-2391.

[27] P. Decleva, M. Brosolo, A. Lisini, and M. Venuti. Continuum Wave Functions by Least-Squares Scheme in a B-Spline Basis: Multicenter and Multielectron Formulations. Int. J. Quant. Chem. v-52, (1994), pp. 507-514.

[28] J.-L. Calais. Wavelets — Something for Quantum Chemistry. Int. J. Quant. Chem. v-58, (1996), pp. 541-548.

[29] P. M. Kozlowski, and E. R. Davidson. One-Electron Properties of Molecules Calculated Using Second-Order Multireference Perturbation Theory. Int. J. Quant. Chem. v-53, (1995), pp. 149-160.

[30] G. G. Hall, and D. Rees A Biscrete Look at Localization. Int. J. Quant. Chem. v-53, (1995), pp. 189-205.

[31] T. Brage, and Ch. F. Fischer. Spline-Galerkin Calculations for Rydberg Series of Calcium. Physica Scripta. v-49, (1995), pp. 651-660.

[32] G. M. Fehrenbach, and H.Bross. Self-Consistent Spline Augmented-Plane-Wave Calculations: Ground-State properties of Си. Phys. Rev. В.: v-48, n-24, (1995), pp. 17703-17714.

[33] Е.Е.Тыртышников. Краткий курс численного анализа. — М.: ВИНИТИ, (1994), — 220с.

[34] Де Бор К. Практическое руководство по сплайнам: Пер. с англ.

— М.: Радио и связь, (1985), — 304с.

[35] JI. Хейгеман, Д. Янг. Прикладные итерационные методы: Пер. с англ. — М.: Мир, (1986), — 448с.

[36] В. Ф. Демьянов, В. Н. Малоземов. Введение в минимакс. М.: Наука, (1972), — 368с.

[37] А.А. Локшин, А.С. Саакян, Ю.И. Тарасов. Параметрические зависимости собственных значений. — М.: МГУ, (1997) — 64с.

[38] Б. Парлетт. Симметричная проблема собственных значений: Пер. с англ. — М.: Мир, (1983), — 384с.

[39] А.А. Локшин, С.Л. Лопатников, Ю.И. Тарасов. Метод сжатых отображений в симметричной проблеме собственных значений.

— М.: МГУ, (1995), — 143с.

[40] А.А. Локшин, Е.А. Сагомонян. Геометрические методы в теории спектров. — М.: МГУ, (1996), — 63с.

[41] I.V. Ibraghimov, Е.Е. Tyrtyshnikov. An Application of Toeplitz Matrices for Quantum Chemistry Problems. / Proceedings of the 9th International Conference "Computational Modelling and Computing in Physics", September 16-21, 1996, Dubna, D5, 11-97-112, (1997), pp. 327-331.

[42] R.C. Agarval, F.G. Gustavson, M. Zubair. A high-performance marix-multiplication algorithm on a distributed-memory parallel computer, using overlapped communication. // IBM J. Res. Dev. v.-38, n.-6, (1994), pp. 673-681.

[43] X. Zang, Y. Yan, K. He. Latency Metric: An Experimental Method for Measuring and Evaluation Parallel Program and Architecture Scalability. //J. Par. Distr. Сотр. v.-22, (1994), pp. 392-410.

[44] S. Horiguchi, W.L. Mirankler. A parallel algorithm for finding the maximum value. // J. Par. Distr. Сотр. v.-lO, (1989), pp. 101-108.

[45] И.В. Ибрагимов. Применение структурированных матриц для решения уравнений Хартри-Фока. / Матричные методы и алгоритмы. — М.: ИВМ РАН, (1998), в печати.

[46] И.В. Ибрагимов. Параллельные алгоритмы БПФ и скалярного произведения векторов. / Матричные методы и алгоритмы. — М.: ИВМ РАН, (1998), в печати.