. Au, itérations de la recherche linéaire (qui, d'après les tests numériques faits en 1D est rarement supérieur à 4), on a au total : 2 l 2 (n + m) + 4 ? lin (n 2 m + n m 2 + n m), expression dans laquelle on peut ne retenir que : 4 ? lin n 2 m Total des opérations pour l'étape globale

E. Cancès, M. Defranceschi, W. Kutzelnigg, C. L. Bris, and Y. Maday, Computational Quantum Chemistry : a Primer, in : Handbook of Numerical Analysis, Special volume, Computational Chemistry, 2003.

R. G. Parr and W. Yang, Density Functional Theory of Atoms and Molecules, 1989.
DOI : 10.1007/978-94-009-9027-2_2

A. Szabo and N. Ostlund, Modern Quantum Chemistry : An Introduction to Advanced Electronic Structure Theory, 1982.

M. Barrault, Développement de méthodes rapides pour le calcul de structures électroniques, 2005.

E. Anglada, E. Artacho, J. M. Junquera, and J. M. Soler, Systematic generation of finite-range atomic basis sets for linear-scaling calculations, Physical Review B, vol.66, issue.20, pp.205101-205104, 2002.
DOI : 10.1103/PhysRevB.66.205101

K. Babu and S. Gadre, Ab initio quality one-electron properties of large molecules: Development and testing of molecular tailoring approach, Journal of Computational Chemistry, vol.80, issue.4, pp.484-495, 2003.
DOI : 10.1002/jcc.10206

R. Baer, Improved Fermi operator expansion methods for fast electronic calculations, J. Chem. Phys, vol.119, pp.4117-4125, 2003.

M. Barrault, E. Cancès, W. W. Hager, and C. L. Bris, Multilevel domain decomposition for electronic structure calculations, Journal of Computational Physics, vol.222, issue.1, pp.86-109, 2007.
DOI : 10.1016/j.jcp.2006.06.049

G. Bencteux, M. Barrault, E. Cancès, W. W. Hager, and C. L. Bris, Domain decomposition and electronic structure computations : a promising approach in : Partial Dierential Equations. Modeling and Numerical Simulation, pp.147-164, 2008.

X. Blanc, A mathematical insight into ab initio simulations of the solid phase, Lecture Notes in Chemistry, vol.74, pp.133-158, 2000.
DOI : 10.1007/978-3-642-57237-1_7

D. R. Bowler, A comparison of linear scaling tight binding methods, Modelling Simul, Mater. Sci. Eng, vol.5, pp.199-222, 1997.

D. Bowler, T. Miyazaki, and M. Gillan, electronic structure techniques, Journal of Physics: Condensed Matter, vol.14, issue.11, pp.2781-2798, 2002.
DOI : 10.1088/0953-8984/14/11/303

D. Bowler, R. Choudhury, M. Gillan, and T. Miyazaki, Recent progress with large-scale ab initio calculations : the CONQUEST code, 2006.

S. F. Boys, Electronic wavefunction I. A general method of calculation for the stationary states of any molecular system, Proc. Roy. Soc. A 200, pp.542-554, 1950.

S. F. Boys, Construction of Some Molecular Orbitals to Be Approximately Invariant for Changes from One Molecule to Another, Reviews of Modern Physics, vol.32, issue.2, pp.296-299, 1960.
DOI : 10.1103/RevModPhys.32.296

E. Cancès and C. L. Bris, Can we outperform the DIIS approach for electronic structure calculations?, International Journal of Quantum Chemistry, vol.110, issue.2, pp.82-90, 2000.
DOI : 10.1002/1097-461X(2000)79:2<82::AID-QUA3>3.0.CO;2-I

M. Challacombe, Linear scaling computation of the Fock matrix. V. Hierarchical Cubature for numerical integration of the exchange-correlation matrix, The Journal of Chemical Physics, vol.113, issue.22, pp.10037-10043, 2000.
DOI : 10.1063/1.1316012

J. R. Chelikowsky, Y. Saad, and N. Trouiller, Finite-difference-pseudopotential method: Electronic structure calculations without a basis, Physical Review Letters, vol.72, issue.8, pp.1240-1243, 1994.
DOI : 10.1103/PhysRevLett.72.1240

L. Colombo and S. Goedecker, Ecient linear scaling algorithm for Tight-Binding molecular dynamics, Phys.Rev. Lett, vol.73, pp.122-125, 1994.

I. Dabo, B. Kozinsky, N. E. Singh-miller, and N. Marzari, Electrostatics in periodic boundary conditions and real-space corrections, Physical Review B, vol.77, issue.11, 2008.
DOI : 10.1103/PhysRevB.77.115139
URL : https://hal.archives-ouvertes.fr/hal-00717151

I. P. Daykov, T. A. Arias, and T. D. , Engeness Robust Ab Initio Calculation of Condensed Matter : Transparent Convergence through Semicardinal Multiresolution Analysis, Phys. Rev. B, vol.90, p.216402

C. Edmiston and K. Ruedenberg, Localized Atomic and Molecular Orbitals. II, The Journal of Chemical Physics, vol.43, issue.10, pp.4916-4919, 1965.
DOI : 10.1063/1.1701520

J. L. Fattebert and J. Bernholc, density-functional theory methods: Optimized nonorthogonal orbitals and multigrid acceleration, Physical Review B, vol.62, issue.3, pp.1713-1722, 2000.
DOI : 10.1103/PhysRevB.62.1713

G. Feng and T. L. Beck, Nonlinear multigrid eigenvalue solver utilizing nonorthogonal localized orbitals, physica status solidi (b), vol.134, issue.5, pp.1054-1062, 2006.
DOI : 10.1002/pssb.200541446

H. Feng, J. Bian, L. Li, and W. Yang, An efficient method for constructing nonorthogonal localized molecular orbitals, The Journal of Chemical Physics, vol.120, issue.20, pp.9458-9466, 2004.
DOI : 10.1063/1.1691396

G. Galli and F. Mauri, Electronic structure calculations and molecular dynamics simulations with linear system size scaling, Physical Review B, vol.50, pp.4316-4326, 1994.

G. Galli, Large-Scale Electronic Structure Calculations Using Linear Scaling Methods, physica status solidi (b), vol.217, issue.1, pp.231-249, 2000.
DOI : 10.1002/(SICI)1521-3951(200001)217:1<231::AID-PSSB231>3.0.CO;2-I

A. Genoni, K. Merz, and M. Sironi, A Hylleraas functional based perturbative technique to relax the extremely localized molecular orbital wavefunction, The Journal of Chemical Physics, vol.129, issue.5, p.54101, 2008.
DOI : 10.1063/1.2961015

L. Genovese, A. Neelov, S. Goedecker, T. Deutsch, S. Ghasemi et al., Daubechies wavelets as a basis set for density functional pseudopotential calculations, The Journal of Chemical Physics, vol.129, issue.1, 2008.
DOI : 10.1063/1.2949547

A. Gibson, R. Haydock, and J. P. Lafemina, electronic-structure computations with the recursion method, Physical Review B, vol.47, issue.15, pp.9229-9237, 1993.
DOI : 10.1103/PhysRevB.47.9229

S. Goedecker, Decay properties of the finite-temperature density matrix in metals, Physical Review B, vol.58, issue.7, pp.3501-3502, 1998.
DOI : 10.1103/PhysRevB.58.3501

S. Goedecker, Linear scaling electronic structure methods, Reviews of Modern Physics, vol.71, issue.4, pp.1085-1123, 1999.
DOI : 10.1103/RevModPhys.71.1085

S. Goedecker, Linear Scaling Methods for the Solution of Schrödinger's Equation, in : Handbook of Numerical Analysis, Special volume, Computational Chemistry, 2003.

N. Govind, Y. Wang, and E. A. Carter, Electronic-structure calculations by first-principles density-based embedding of explicitly correlated systems, The Journal of Chemical Physics, vol.110, issue.16, p.7677, 1999.
DOI : 10.1063/1.478679

R. J. Harrison, G. I. Fann, T. Yanai, Z. Gan, and G. Beylkin, Multiresolution quantum chemistry: Basic theory and initial applications, The Journal of Chemical Physics, vol.121, issue.23, p.11587, 2004.
DOI : 10.1063/1.1791051

V. Heine, SOLID STATE PHYSICS, 1980.
DOI : 10.1016/B978-0-08-009242-3.50013-7

R. Homann, An Extended Hückel Theory. I. Hydrocarbons, J. Chem. Phys, vol.39, 1397.

C. Jacob, J. Neugebauer, and L. Visscher, A flexible implementation of frozen-density embedding for use in multilevel simulations, Journal of Computational Chemistry, vol.125, issue.6, pp.1011-1018, 2008.
DOI : 10.1002/jcc.20861

B. Jansik, S. Host, P. Jorgensen, J. Olsen, and T. Helgaker, Linear-scaling symmetric square-root decomposition of the overlap matrix, The Journal of Chemical Physics, vol.126, issue.12, p.124104, 2007.
DOI : 10.1063/1.2709881

W. Kohn, Analytic Properties of Bloch Waves and Wannier Functions, Physical Review, vol.115, issue.4, pp.809-821, 1959.
DOI : 10.1103/PhysRev.115.809

W. Kohn, Density Functional and Density Matrix Method Scaling Linearly with the Number of Atoms, Physical Review Letters, vol.76, issue.17, pp.3168-3171, 1996.
DOI : 10.1103/PhysRevLett.76.3168

J. Korchowiec, F. L. Gu, A. Imamura, B. Kirtman, and Y. Aoki, Elongation method with cutoff technique for linear SCF scaling, International Journal of Quantum Chemistry, vol.114, issue.5, pp.785-794, 2005.
DOI : 10.1002/qua.20448

X. Li, R. W. Nunes, and D. Vanderbilt, Density-matrix electronic-structure method with linear system-size scaling, Physical Review B, vol.47, issue.16, pp.10891-10894, 1993.
DOI : 10.1103/PhysRevB.47.10891

N. Marzari and D. Vanderbilt, Maximally localized generalized Wannier functions for composite energy bands, Physical Review B, vol.56, issue.20, pp.12847-12865, 1997.
DOI : 10.1103/PhysRevB.56.12847

P. Maslen, C. Ochsenfeld, C. A. White, M. S. Lee, and M. Head-gordon, Locality and Sparsity of Ab Initio One-Particle Density Matrices and Localized Orbitals, Locality and Sparsity of Ab Initio One-particle Density Matrices and Localized Orbitals, pp.2215-2222, 1998.
DOI : 10.1021/jp972919j

T. Miyazaki, D. R. Bowler, R. Choudhury, and M. J. Gillan, Density functional calculations of Ge(105) : Local basis sets and O(N) methods, Phys. Rev, p.115327, 2007.

A. M. Niklasson, Expansion algorithm for the density matrix, Physical Review B, vol.66, issue.15, pp.155115-155120, 2002.
DOI : 10.1103/PhysRevB.66.155115

R. Nunes and D. Vanderbilt, Generalization of the density-matrix method to a nonorthogonal basis, Physical Review B, vol.50, issue.23, pp.17611-17614, 1994.
DOI : 10.1103/PhysRevB.50.17611

P. Ordejón, D. A. Drabold, M. D. Grumbach, and R. M. Martin, Unconstrained minimization approach for electronic computations that scales linearly with system size, Physical Review B, vol.48, issue.19, pp.14646-14649, 1993.
DOI : 10.1103/PhysRevB.48.14646

P. Ordejón, D. A. Drabold, R. M. Martin, and M. D. Grumbach, Linear system-size scaling methods for electronic-structure calculations, Physical Review B, vol.51, issue.3, pp.1456-1476, 1995.
DOI : 10.1103/PhysRevB.51.1456

P. Ordejón, Order-N tight-binding methods for electronic-structure and molecular dynamics, Computational Materials Science, vol.12, issue.3, pp.157-191, 1998.
DOI : 10.1016/S0927-0256(98)00027-5

J. E. Pask and P. A. Sterne, Finite elements in ab initio electronicstructure calculations, Handbook of Materials, p.423, 2005.

A. Palser and D. Manopoulos, Canonical purification of the density matrix in electronic-structure theory, Physical Review B, vol.58, issue.19, pp.12704-12711, 1998.
DOI : 10.1103/PhysRevB.58.12704

J. Pipek and P. Mezey, and semiempirical linear combination of atomic orbital wave functions, The Journal of Chemical Physics, vol.90, issue.9, p.4916, 1989.
DOI : 10.1063/1.456588

M. J. Rayson and P. R. Briddon, Rapid iterative method for electronic-structure eigenproblems using localised basis functions, Computer Physics Communications, vol.178, issue.2, pp.128-134, 2008.
DOI : 10.1016/j.cpc.2007.08.007

M. J. Rayson, electronic structure calculations without localization, Physical Review B, vol.75, issue.15, p.153203, 2007.
DOI : 10.1103/PhysRevB.75.153203

E. H. Rubensson and P. Salek, Systematic sparse matrix error control for linear scaling electronic structure calculations, Journal of Computational Chemistry, vol.13, issue.15, pp.1628-1637, 2005.
DOI : 10.1002/jcc.20315

E. H. Rubensson, E. Rudberg, and P. Salek, Systematic sparse matrix error control for linear scaling electronic structure calculations, Journal of Computational Chemistry, vol.13, issue.15, pp.1628-1637, 2008.
DOI : 10.1002/jcc.20315

E. H. Rubensson, N. Bock, E. Holmström, and A. Niklasson, Recursive inverse factorization, The Journal of Chemical Physics, vol.128, issue.10, 2008.
DOI : 10.1063/1.2884921

P. Salek, S. Host, L. Thogersen, P. Jorgensen, P. Manninen et al., Linear-scaling implementation of molecular electronic self-consistent field theory, The Journal of Chemical Physics, vol.126, issue.11, p.114110, 2007.
DOI : 10.1063/1.2464111

R. Schneider, T. Rohwedder, A. Neelov, and J. Blauert, Direct minimization for calculating invariant subspaces in density functional computations of the electronic structure, 2008.

F. Shimojo, R. K. Kalia, A. Nakano, and P. Vashishta, Embedded divideand-conquer algorithm on hierarchical real-space grids : parallel molecular dynamics simulation based on linear-scaling density functional theory, pp.151-164, 2005.

F. Shimojo, R. K. Kalia, A. Nakano, and P. Vashishta, Divide-and-conquer density functional theory on hierarchical real-space grids: Parallel implementation and applications, Physical Review B, vol.77, issue.8, p.85103, 2008.
DOI : 10.1103/PhysRevB.77.085103

E. Schwegler and M. , Challacombe Linear scaling computation of the Fock matrix, Theor. Chem. Acc, vol.104, p.344349, 2000.

S. Schweizer, J. Kussmann, B. Doser, and C. Ochsenfeld, Linear-scaling Cholesky decomposition, Journal of Computational Chemistry, vol.71, issue.6, pp.1004-1010, 2008.
DOI : 10.1002/jcc.20862

L. Seijo and Z. Barandiarán, Parallel, linear-scaling building-block and embedding method based on localized orbitals and orbital-specific basis sets, The Journal of Chemical Physics, vol.121, issue.14, p.6698, 2004.
DOI : 10.1063/1.1786911

L. Seijo, Z. Barandiarán, and J. M. Soler, Order-N and embedded-cluster first-principles DFT calculations using SIESTA/Mosaico, Theoretical Chemistry Accounts, vol.121, issue.3, p.541, 2007.
DOI : 10.1007/s00214-007-0338-y

C. Skylaris and P. D. Haynes, Achieving plane wave accuracy in linear-scaling density functional theory applied to periodic systems: A case study on crystalline silicon, The Journal of Chemical Physics, vol.127, issue.16, p.164712, 2007.
DOI : 10.1063/1.2796168

E. Tsuchida, Augmented Orbital Minimization Method for Linear Scaling Electronic Structure Calculations, Journal of the Physical Society of Japan, vol.76, issue.3, p.34708, 2007.
DOI : 10.1143/JPSJ.76.034708

E. Tsuchida, molecular dynamics simulations with linear scaling: application to liquid ethanol, Journal of Physics: Condensed Matter, vol.20, issue.29, p.294212, 2008.
DOI : 10.1088/0953-8984/20/29/294212

J. Vandevondele and J. Hutter, Gaussian basis sets for accurate calculations on molecular systems in gas and condensed phases, The Journal of Chemical Physics, vol.127, issue.11, pp.114105-114106, 2007.
DOI : 10.1063/1.2770708

L. Wang, Z. Zhao, and J. Meza, Linear-scaling three-dimensional fragment method for large-scale electronic structure calculations, Physical Review B, vol.77, issue.16, 2008.
DOI : 10.1103/PhysRevB.77.165113

V. Weber, J. Vandevondele, J. Hutter, and A. M. Niklasson, Direct energy functional minimization under orthogonality constraints, The Journal of Chemical Physics, vol.128, issue.8, pp.84113-84114, 2008.
DOI : 10.1063/1.2841077

V. Weber and J. Hutter, A smooth ???1-norm sparseness function for orbital based linear scaling total energy minimization, The Journal of Chemical Physics, vol.128, issue.6, p.64107, 2008.
DOI : 10.1063/1.2828507

C. A. White, P. Maslen, M. S. Lee, and M. Head-gordon, The tensor properties of energy gradients within a non-orthogonal basis, Chemical Physics Letters, vol.276, issue.1-2, pp.133-138, 1997.
DOI : 10.1016/S0009-2614(97)88046-3

W. Yang and T. Lee, A density???matrix divide???and???conquer approach for electronic structure calculations of large molecules, The Journal of Chemical Physics, vol.103, issue.13, pp.5674-5678, 1995.
DOI : 10.1063/1.470549

A. Björck, Numerical Methods for least squares problems, 1996.
DOI : 10.1137/1.9781611971484

B. N. Parlett, The Symmetric Eigenvalue Problem, 1980.
DOI : 10.1137/1.9781611971163

P. Arbenz, U. L. Hetmaniuk, R. B. Lehoucq, and R. S. Tuminaro, A comparison of eigensolvers for large-scale 3D modal analysis using AMG-preconditioned iterative methods, International Journal for Numerical Methods in Engineering, vol.26, issue.198, pp.204-236, 2005.
DOI : 10.1002/nme.1365

M. Benzi and N. Razouk, Decay bounds and O(n) algorithms for approximating functions of sparse matrices, pp.16-39, 2007.

C. Bischof and G. Quintana-orti, Computing rank-revealing QR factorizations of dense matrices, ACM Transactions on Mathematical Software, vol.24, issue.2, pp.226-253, 1998.
DOI : 10.1145/290200.287637

J. Demmel, O. Marques, B. N. Parlett, and C. Vömel, Performance and Accuracy of LAPACK's Symmetric Tridiagonal Eigensolvers, SIAM Journal on Scientific Computing, vol.30, issue.3, pp.1508-1526, 2008.
DOI : 10.1137/070688778

Z. Drma£, On the Failure of Rank-Revealing QR Factorization Software -- A Case Study, ACM Transactions on Mathematical Software, vol.35, issue.2, p.12, 2008.
DOI : 10.1145/1377612.1377616

W. Hager and H. , A New Conjugate Gradient Method with Guaranteed Descent and an Efficient Line Search, SIAM Journal on Optimization, vol.16, issue.1, pp.170-192, 2005.
DOI : 10.1137/030601880

U. L. Hetmaniuk and R. B. Lehoucq, Multilevel Methods for Eigenspace Computations in Structural Dynamics, Proceedings of the 16th International Conference on Domain Decomposition Methods, Courant Institute, 2005.
DOI : 10.1007/978-3-540-34469-8_9

C. and L. Bris, Computational chemistry from the perspective of numerical analysis, Acta Numerica, vol.14, pp.363-444, 2005.
DOI : 10.1017/S096249290400025X

C. Paige and M. Saunders, Solution of Sparse Indefinite Systems of Linear Equations, SIAM Journal on Numerical Analysis, vol.12, issue.4, pp.617-629, 1975.
DOI : 10.1137/0712047

Y. Zhou and Y. Saad, Block Krylov???Schur method for large symmetric eigenvalue problems, Numerical Algorithms, vol.12, issue.5, pp.341-359, 2008.
DOI : 10.1007/s11075-008-9192-9

D. C. Sorensen, Newton???s Method with a Model Trust Region Modification, SIAM Journal on Numerical Analysis, vol.19, issue.2, pp.409-426, 1982.
DOI : 10.1137/0719026

C. Yang, J. C. Meza, and L. Wang, A Trust Region Direct Constrained Minimization Algorithm for the Kohn???Sham Equation, SIAM Journal on Scientific Computing, vol.29, issue.5, pp.1854-1875, 2007.
DOI : 10.1137/060661442

N. Bock, E. Rubensson, P. Salek, A. Niklasson, and M. Challacombe, Cache oblivious storage and access heuristics for blocked matrix-matrix multiplication, 2008.

D. Bowler, T. Miyazaki, and M. Gillan, Parallel sparse matrix multiplication for linear scaling electronic structure calculations, Computer Physics Communications, vol.137, issue.2, pp.255-273, 2001.
DOI : 10.1016/S0010-4655(01)00164-3

W. P. Petersen and P. Arbenz, Introduction to Parallel Computing, 2004.

E. Rubensson, E. Rudberg, and P. Salek, A hierarchic sparse matrix data structure for large-scale Hartree-Fock/Kohn-Sham calculations, Journal of Computational Chemistry, vol.21, issue.16, pp.2531-2537, 2007.
DOI : 10.1002/jcc.20691

C. Saravanan, Y. Shao, R. Baer, P. Ross, and M. Head-gordon, Sparse matrix multiplications for linear scaling electronic structure calculations in an atom-centered basis set using multiatom blocks, Journal of Computational Chemistry, vol.257, issue.5, pp.618-622, 2003.
DOI : 10.1002/jcc.10224