Cornell University

Department of Physics

Phys 480/680, Astro 690 March 16, 2007

Computational Physics, Spring 2007

Homework Assignment # 6

(Due Wed, April 4 at 5:00pm)

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:

• Lec 13, 03/08 (Thu) Introduction to numerical linear algebra; Benefits of LAPACK; Solution of linear systems through LU decomposition and back substitution; Crout's algorithm for LU decomposition
  Reading: NR 2.0, 2.3

• Lec 14, 03/13 (Tue) Crout's Algorithm with pivoting; Begin unit on code optimization: Amdahl's law, Theoretical peal performance, inner loop tricks, cache and definition of associated concepts
  Reading: NR 2.3

• Lab 5, 03/15 (Thu) *NOTE* NO LECTURE GO DIRECTLY TO LAB: Profiling and real-time optimization of full atomic solver-- using gprof; avoiding malloc; inlining optimizations.
• Twenty minute minilecture, 03/15 (Thu) Consequences of cache, random versus sequential access, impact on ordering of loops in vector-matrix multiplication.

• 03/20, 03/22 SPRING BREAK

Preview:

• 03/27 Lec 15 (Tue) Memory access overhead factor, BLAS1-3, blocked matrix multiplies; Automated empirical optimization of software (AEOS): automatically tuned linear algebra software (ATLAS), fastest Fourier Transform in the West (FFTW).

• 03/29 Lec 16 (Thu) 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/03 Lec 17 (Tue): Choice of planewave basis for Poisson's equation; form of operators and transforms in a plane-wave basis; octave/matlab notations.

• 04/05 Lec 18 (Thu): Discrete Fourier Transforms: standard ordering of indices for Discrete Fourier Transforms (DFTs); aliasing/Nyquist frequency

• 04/05 Lab 6 (Thu) FLOP performance of basic operations; FLOP rates in octave.

• 04/10 Lec 19 (Tue) Fourier factorization and inversion theorems; Eigenvalue problems in $d>1$ dimension: variational principle, analytic continuation for constraints, minimization by steepest descents
  Reading: NR 10.0

• 04/12 Lec 20 (Thu) 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/12 Lab 7 (Thu) Spectral solution of Poisson's equation

• 04/17 Lec 21 (Tue) Converge of steepest descents; preconditioning; line minimization; motivation for conjugate gradients
  Reading: NR 10.2, 10.3. 10.5
• 04/19 Lec 22 (Thu) Conjugate gradient algorithm
  Reading: 10.6
• 04/19 Lab 8 (Thu) Spectral solution of Schrödinger's equation

• 04/24 Lec 23 (Tue) FFT
  Reading: 12.2
• 04/26 Lec 24 (Thu) Further optimizations for spectral methods; ab initio pseudopotentials
• 04/26 Lab 9 (Thu) Performance of numerical minimization techniques; preconditioner for quantum calculations

• 05/02 Lec 25 (Tue) Extraction of eigenstates from variational principle
• 05/04 Lab 10 (Thu) Physics of harmonic oscillator, H2 molecule and germanium solid

Postscript Version

PDF Version