Cornell University

Department of Physics

Phys 480/680, Astro 690 March 29, 2006

Computational Physics, Spring 2006

Homework Assignment # 6

(Due Wed, April 5)

Agenda and readings:

Goal: Optimize to produce efficient, high-precision software to calculate the electronic structure of atoms within density-functional theory; explore FLOP rates of various operations and cache performance.

Readings marked NR are from Numerical Recipes: The Art of Scientific Computing, 2$^{\mathrm nd}$ edition (in C). Readings marked LN are from the course lecture notes to be found at http://www.muchomas.lassp.cornell.edu/P480.

Recap of last few weeks:

• 02/28 Lec 11: Solution of many non-linear equations in many unknowns, mixing method, convergence rates, condition numbers; Newton-Raphson and Broyden approaches; motivation for a ``modified'' Broyden's method for large systems of equations
  Readings: NR 9.6-9.7

• 03/02 Lec 12: Modified Broyden method

• 03/07 Lec 13: Introduction to numerical linear algebra; Benefits of LAPACK; Solution of linear systems through LU decomposition and backsubsitution
  Reading: NR 2.0, 2.3

• 03/09 Lec 14: Crout's Algorithm with and without pivoting
  Reading: NR 2.3

• 03/09 Lab 4: ``Hot-wired'' solver for atoms within Hartree theory.

• 03/14 LECTURE CANCELLED: APS Meeting

• 03/16 Lec 15: Ahmdal's law, Identification of innermost loop, CPU performance terminology, Tricks and timings for innermost loop operations, Cache terminology and implications, Avoiding cache misses.

• 03/20-03/24 SPRING BREAK

• 03/28 Lab 5 (Met early, 8:00am!!!): Code timing, profiling and optimization; avoiding system calls, inlining of functions, compiler options.

• 03/28 Lec 16 (9:15-9:55am): Memory access overhead factor, reuse of data while in cache, blocked matrix multiplication.

Preview of rest of the semester:

• 03/30 Lec 17: BLAS1-3, blocked matrix multiplies; Automated empirical optimization of software (AEOS), automatically tuned linear algebra software (ATLAS), fastest Fourier Transform in the West (FFTW). Solution of Poisson's equation in d>1 dimensions; expressive software; solution to Poisson's equation in a single line of code; choice of plane-wave (complex exponential) basis for periodic boundary conditions.

• 04/04 Lec 18: Form of operators and transforms in a plane-wave basis; octave/matlab notations; standard ordering of indices for Discrete Fourier Transforms (DFTs).
• 04/06 Lec 19: Discrete Fourier Transforms: aliasing/Nyquist frequency, Fourier factorization theorem
  Reading: NR 12.0, 12.1, 12.4
• 04/06 Lab 7: FLOP performance of basic operations; FLOP rates in octave.

• 04/11 Lec 20: Fourier inversion theorem; Eigenvalue problems in $d>1$ dimension: variational principle, analytic continuation for constraints, minimization by steepest descents
  Reading: NR 10.0
• 04/13 Lec 21: DFT++ expressions for energy and gradient for multiple states and for density functional theory
  Reading: Sections 1-4 of http://arxiv.org/abs/cond-mat/9909130
• 04/13 Lab 8: Spectral solution of Poisson's equation

• 04/18 Lec 22: Converge of steepest descents; preconditioning; line minimization; motivation for conjugate gradients
  Reading: NR 10.2, 10.3. 10.5
• 04/20 Lec 23: Conjugate gradient algorithm
  Reading: 10.6
• 04/20 Lab 9: Spectral solution of Schrödinger's equation

• 04/25 Lec 24: FFT
  Reading: 12.2
• 04/27 Lec 25: Further optimizations for spectral methods; ab initio pseudopotentials
• 04/27 Lab 10: Performance of numerical minimization techniques; preconditioner for quantum calculations

• 05/02 Lec 26: Extraction of eigenstates from variational principle
• 05/04 Lab 11: Physics of harmonic oscillator, H2 molecule and germanium solid

Postscript Version

PDF Version