Numerical solution of the Hartree-Fock equation by multilevel tensor-structured methods vorgelegt von Diplom-Physikerin Venera Khoromskaia Stadt Kazan, Russland Von der Fakult¨at II - Mathematik und Naturwissenschaften der Technischen Universit¨at Berlin zur Erlangung des akademisches Grades Doktor der Naturwissenschaften Dr.rer.nat. genehmigte Dissertation Promotionausschuss: Vorsitzender: Prof. Dr. J. Blath Berichter/Gutachter: Prof. Dr. Reinhold Schneider Berichter/Gutachter: Prof. Dr. Dr. h.c. Wolfgang Hackbusch zus¨atzlicher Gutachter: Prof. Dr. Eugene Tyrtyshnikov Tag der mu¨ndlichen Pru¨fung: 10 December 2010 Berlin 2011 D 83 2 Acknowledgements I would like to express my gratitude to Prof. Dr. Reinhold Schneider for su- pervising my PhD project, for fruitful discussions and his friendly encouragement during the work on this project. His interest and expertise in the research topics related to the Hartree-Fock equation and the density functional theory motivated much of therecent progress inthealgebraictensor methods inelectronic structure calculations. I would like to thank Prof. Dr. Dr. h.c. Wolfgang Hackbusch for valuable discussions and excellent conditions for performing research at the Max-Planck- Institute for Mathematics in the Sciences. This work is done due to fruitful collaboration with Dr. Heinz-Ju¨rgen Flad. I appreciate very much his kind encouragement and support of my work and always beneficial and stimulating discussions owing to his thorough expertise in modern quantum chemistry. Professional assistance ofPD DrSci. BorisKhoromskij intheresearch ontensor numerical methods helped me to make an active start in a new field. I acknowl- edge him for the statement of some research problems and for proofreading the manuscript. I kindly acknowledge Prof. Eugene Tyrtyshnikov, Prof. Dr. Christian Lu- bich and Prof. Dr. Lars Grasedyck, for their interest to my work and for the opportunity to give talks at recent conferences and seminars on tensor methods. I amvery much appreciative to Prof. Dr. IvanGavrilyuk for his encouragement and interest to my work. I would like to thank my colleagues at the Max-Planck-Institute in Leipzig, Dr. Ronald Kriemann, Dr. Jan Schneider, Dr. Kishore Kumar Naraparaju, Dr. Sambasiva Rao Chinnamsetty, Dr. Hongjun Luo, Dr. Thomas Blesgen, Dr. Lehel Banjai, Dipl.-Math. Konrad Kaltenbach, Dipl.-Math. Stephan Schwinger, Dipl.-Math. Florian Drechsler and colleagues at the TU Berlin, Prof. Dr. Harry Yserentant, Dipl.-Math. Fritz Kru¨ger and Dipl.-Math. Andr´e Ushmaev for inter- esting discussions. I would like to acknowledge the colleagues from the Institute of Numerical Mathematics of the Russian Academy of Science in Moscow, Dr. Ivan Oseledets and Dr. Dmitrij Savostyanov for stimulating discussions. I would like to thank Prof. Vikram Gavini (University of Michigan) for pro- ductive collaboration and for the data on electron density of large Aluminium clusters. Kind assistance of the librarians Mrs. Britta Schneemann and Mrs. Katarzyna Baier was very helpful during my work. I would like to thank cordially the 3 secretaries at the Max-Planck-Institute and TU Berlin, Mrs. Valeria Hu¨nniger and Mrs. Susan Kosub for their helpful technical support. 4 Numerische L¨osung der Hartree-Fock-Gleichung mit mehrstufigen Tensor-strukturierten Verfahren Venera Khoromskaia Abstract der PhD Dissertation DiegenaueL¨osungderHartree-Fock-Gleichung(HFG),dieeinnichtlinearesEigen- wertproblem in R3 darstellt, ist infolge der nichtlokalen Intergraltransformationen und der scharfen Peaks in der Elektronendichte und den Moleku¨lorbitalen eine herausfordernde numerische Aufgabe. Aufgrund der nichtlinearen Abh¨angigkeit der Hamilton-Matrix von den Eigenvektoren, ist das Problem nur iterativ l¨osbar. Die traditionelle L¨osung der HFG basiert auf einer analytischen Berechnung der auftretenden Faltungsintegrale im R3 mit Hilfe von dem Problem angepassten Basen (so genannte Zwei-Elektron-Integrale). Die inh¨arenten Grenzen dieses Konzepts werden wegen der starken Abh¨angigkeit der numerischen Effizienz von der Gr¨oße und den Eigenschaften der analytisch separablen Basis sichtbar. IndieserDissertationwurdenneuegitter-basiertemehrstufigeTensor-strukturierte Verfahren entwickelt und anhand der numerischen L¨osung der HFG getestet. Diese Methoden beinhalten effiziente Algorithmen zur Darstellung diskretisierter Funktionen und Operatoren in R3 durch strukturierte Tensoren in den kanonis- chen,Tucker-undkombiniertenTensorformatenmiteinerkontrollierbarenGenauigkeit sowie schnelle entsprechenden Operationen fu¨r multilineare Tensoren. Insbeson- dere wird die beschleunigte Mehrgitter-Rang-Reduktion des Tensors vorgestellt, die auf der reduzierten Singul¨arwertzerlegung h¨oherer Ordnung basiert. Der Kern der Anwendung dieser Verfahren fu¨r die L¨osung der HFG ist die Ver- wendung strukturierter Tensoren zur genauen Berechnung der Elektronendichte und der nichtlinearen Hartree- und (nichtlokalen) Austauschoperatoren in R3, die in jedem Iterationsschritt auf einer Reihenfolge von n n n kartesischen × × Gittern darstellt wurden. Somit wurden die entsprechenden sechs-dimensionalen Integrationen durch multilineare algebraische Operationen wie das Skalar- und Hadamardprodukt, die dreidimensionale Faltungstransformation und die Rang- Reduktionfu¨rTensorendritterOrdnungersetzt,dieann¨aherndmitO(n)-Komplexit¨at implementiert wurden, wobei n die eindimensionale Gittergr¨oße ist. Daher ist der wesentliche Vorteil unserer Tensor-strukturierten Verfahren, dass die gitter- basierte Berechnung von Integraloperatoren in Rd, d 3, lineare Komplexit¨at in ≥ n hat. Man beachte, dass im Sinne der u¨bliche Absch¨atzung mittels des Gitter- volumens N = n3 die Operationen mit strukturierten Tensoren eine sublineare vol 1/3 Komplexit¨at haben, O(N ). vol Das vorgestellte ”‘grey-box”’-Schema zur L¨osung der HFG erfordert keine an- alytischen Vorberechnungen der Zwei-Elektron-Integrale. Weiterhin ist dieses 5 Schema sehr flexibel hinsichtlich der Wahl der gitter-orientierten Basisfunktio- nen. Numerische Berechnungen am Beispiel des “all electron” Falls fu¨r H O, CH 2 4 und C H und des Pseudopotentialfalls fu¨r CH OH and C H OH Moleku¨le zeigen 2 6 3 2 5 die geforderte hohe Genauigkeit. Die Tensor-strukturierten Verfahren k¨onnen auch zur L¨osung der Kohn-Sham- Gleichung angewandt werden, indem anstelle einer problem-unabh¨angigen Basis, wie die der ebenen Wellen oder einer großen Anzahl finiter Elemente im R3, eine geringe Anzahl problem-orientierter rang-strukturierter algebraischer Basisfunk- tionen verwendet werden, die auf einem Tensorgitter dargestellt sind. 6 Numerical solution of the Hartree-Fock equation by multilevel tensor-structured methods Venera Khoromskaia Abstract of PhD dissertation An accurate solution of the Hartree-Fock equation, a nonlinear eigenvalue prob- lem in R3, is a challenging numerical task due to the presence of nonlocal integral transforms and strong cusps in the electron density and molecular orbitals. In view of the nonlinear dependence of the Hamiltonian matrix on the eigenvec- tors, this problem can only be solved iteratively, by self-consistent field iterations. Traditionally, the solution of the Hartree-Fock equation is based on rigorous an- alytical precomputation of the arising convolution type integrals in R3 in the naturally separable basis (so-called two-electron integrals). Inherent limitations of this concept are evident because of the strong dependence of the numerical efficiency on the size and approximation quality of the problem adapted basis sets. In this dissertation, novel grid-based multilevel tensor-structured methods are developed andtested by a numerical solutionof theHartree-Fockequation. These methods include efficient algorithms for the low-rank representation of discretized functions and operators in R3, in the canonical, Tucker and mixed tensor formats with a controllable accuracy, and fast procedures for the corresponding multilin- ear tensor operations. In particular, a novel multigrid accelerated tensor rank reduction method is introduced, based on the reduced higher order singular value decomposition. The core of our approach to the solution of the Hartree-Fock equation is the accurate tensor-structured computation of the electron density and the nonlinear Hartree and the (nonlocal) exchange operators in R3, discretized on a sequence of n n n Cartesian grids, at every step of nonlinear iterations. Hence, the × × corresponding six-dimensional integrations are replaced by multilinear algebra operations such as the scalar and Hadamard products, the 3D convolution trans- form, and the rank truncation for 3rd order tensors, which are implemented with an almost O(n)-complexity, where n is the univariate grid size. In this way, the basic advantage of our tensor-structured methods is the grid-based evaluation of integral operators in Rd, d 3, with linear complexity in n. Note that in terms ≥ of usual estimation by volume size N = n3, the tensor-structured operations vol 1/3 are of sublinear complexity, O(N ). vol The proposed “grey-box” scheme for the solution of the Hartree-Fock equation does not require analytical precomputation of two-electron integrals. Also, this scheme is very flexible to the choice of grid-based separable basis functions. 7 Numerical illustrations for all electron case of H O, CH , C H and pseudopo- 2 4 2 6 tential case of CH OH and C H OH molecules demonstrate the required high 3 2 5 accuracy of calculations and an almost linear computational complexity in n. The tensor-structured methods can be also applied to the solution of the Kohn- Sham equation, where instead of problem-independent bases like plane waves or a large number of finite elements in R3, one can use much smaller set of problem adapted basis functions specified on a tensor grid. 8 Contents 1 Introduction 11 2 Tensor structured (TS) methods for functions in Rd, d 3 27 ≥ 2.1 Definitions of rank-structured tensor formats . . . . . . . . . . . . 28 2.1.1 Full format dth order tensors . . . . . . . . . . . . . . . . 28 2.1.2 Tucker, canonical and mixed (two-level) tensor formats . . 30 2.2 Best orthogonal Tucker approximation (BTA) . . . . . . . . . . . 34 2.2.1 General discussion . . . . . . . . . . . . . . . . . . . . . . 34 2.2.2 BTA algorithm for full format tensors . . . . . . . . . . . . 37 2.2.3 BTA for rank-R canonical input . . . . . . . . . . . . . . . 40 2.2.4 Mixed BTA for full format and Tucker tensors . . . . . . . 45 2.2.5 Remarks on the Tucker-to-canonical transform . . . . . . . 48 2.3 Numerics on BTA of function related tensors in R3 . . . . . . . . 50 2.3.1 General description . . . . . . . . . . . . . . . . . . . . . . 50 2.3.2 Numerics for classical potentials . . . . . . . . . . . . . . . 51 2.3.3 Application to functions in electronic structure calculations 61 2.4 Tensorisation of basic multilinear algebra (MLA) operations . . . 65 2.4.1 Some bilinear operations in the Tucker format . . . . . . . 66 2.4.2 Summary on MLA operations in rank-R canonical format . 68 3 Multigrid Tucker approximation of function related tensors 71 3.1 Motivations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 3.2 Multigrid accelerated BTA of canonical tensors . . . . . . . . . . 72 3.2.1 Basic concept . . . . . . . . . . . . . . . . . . . . . . . . . 72 3.2.2 Description of the Algorithm and complexity bound . . . . 75 3.2.3 Numerics on rank reduction of the electron density ρ . . . 78 3.3 MultigridacceleratedBTAforthefullformatfunctionrelatedtensors 82 3.3.1 Numerics on the MGA Tucker approximation (ρ1/3) . . . . 83 3.3.2 BTA of the electron density of Aluminium clusters . . . . 85 4 TS computation of the Coulomb and exchange Galerkin matrices 89 4.1 General remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 9 Contents 4.2 Accurate evaluation of the Hartree potential by the tensor-product convolution in R3 . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 4.3 Tensor computation of the Coulomb matrix . . . . . . . . . . . . 100 4.4 Numerics: the Coulomb matrices of CH , C H and H O molecules 100 4 2 6 2 4.5 Agglomerated computation of the Hartree-Fock exchange . . . . . 106 4.5.1 Galerkin exchange operator in the Gaussian basis . . . . . 107 4.5.2 Discrete computational scheme . . . . . . . . . . . . . . . 109 4.6 Numericals experiments . . . . . . . . . . . . . . . . . . . . . . . 117 4.6.1 All electron case . . . . . . . . . . . . . . . . . . . . . . . 117 4.6.2 Pseudopotential case . . . . . . . . . . . . . . . . . . . . . 118 5 Solution of the Hartree-Fock equation by multilevel TS methods 119 5.1 Galerkin scheme for the Hartree-Fock equation . . . . . . . . . . . 121 5.1.1 Problem setting . . . . . . . . . . . . . . . . . . . . . . . . 121 5.1.2 Traditional discretization . . . . . . . . . . . . . . . . . . 122 5.1.3 Novel scheme via agglomerated tensor-structured calcula- tion of Galerkin matrices . . . . . . . . . . . . . . . . . . . 124 5.2 Multilevel tensor-truncated iteration via DIIS . . . . . . . . . . . 126 5.2.1 General SCF iteration . . . . . . . . . . . . . . . . . . . . 126 5.2.2 SCF iteration by using DIIS scheme . . . . . . . . . . . . . 126 5.2.3 Unigrid and multilevel tensor-truncated DIIS iteration . . 127 5.2.4 Complexity estimates in terms of R , N and n . . . . . . 129 0 orb 5.3 Numerical illustrations . . . . . . . . . . . . . . . . . . . . . . . . 131 5.3.1 General discussion . . . . . . . . . . . . . . . . . . . . . . 131 5.3.2 Multilevel tensor-truncated SCF iteration applied to some moderate size molecules . . . . . . . . . . . . . . . . . . . 132 5.3.3 Conclusions to Section 5 . . . . . . . . . . . . . . . . . . . 134 6 Summary of main results 137 6.1 Brief summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 6.2 Presentations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 7 Appendix 143 7.1 Singular value decomposition and the best rank-k approximation of a matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 7.2 Reduced SVD of a rank-R matrix . . . . . . . . . . . . . . . . . . 143 7.3 List of abbreviations . . . . . . . . . . . . . . . . . . . . . . . . . 145 Bibliography 145 10