Master class Validation in scientific computing
Master in Computer Science, École Normale Supérieure de Lyon, 2006-2007
Nathalie Revol (INRIA, LIP, École Normale Supérieure de Lyon)

Description of this course, along with some general references.

• Planning
• Bibliography
• Lecture notes
• Misc

Planning

Monday: 13h30 - 15h30, B1
Thursday: 10h15 - 12h15, B1
Friday: 10h15 - 12h15, B1

References

• D. Goldberg: What every computer scientist should know about floating-point arithmetic, ACM Computing Surveys, vol 23, no 1, pp 5–48, 1991.
• W. Kahan: How Futile are Mindless Assessments of Roundoff in Floating-Point Computations?, Householder Symposium XVI, May 2005, text available here.
• Ph. Langlois: Chap. 1 : Introduction générale, in A. Barraud et al.: Outils d'analyse numérique pour l'automatique, pp 19–52, Traité IC2. Hermès Science, 2002.
• N. Higham: Accuracy and Stability of Numerical Algorithms, SIAM Press, 2nd edition, 2003.
• J.-M. Chesneaux et F. Jézéquel: Théorie et pratique de l'arithmétique stochastique discrète, Réseaux et systèmes répartis - calculateurs parallèles, vol 13, no 4-5, pp 485-504, 2001.
• P. Zimmermann: Arithmétique en précision arbitraire, Réseaux et systèmes répartis - calculateurs parallèles, vol 13, no 4-5, pp 357–386, 2001. Également disponible sous forme de rapport de recherche INRIA 4272 http://www.inria.fr/rrrt/rr-4272.html, septembre 2001,
• G. Alefeld and G. Mayer: Interval analysis: theory and applications, Journal of Computational and Applied Mathematics, vol 121, pp 421–464, 2000.
• J. von zur Gathen and J. Gerhard: Modern Computer Algebra, Cambridge University Press, 2nd edition, 2003.

• S. Funke, K. Mehlhorn: LOOK: A Lazy Object-Oriented Kernel design for geometric computation, Computational Geometry, vol 22, pp. 99-118, 2002.
• K.O. Geddes and W.W. Zheng: Exploiting fast hardware floating point in high precision computation, Proceeding ISSAC 2003, pp 111-118.
  Complements: chapter 7 on Iterative refinement, N. Higham: Accuracy and Stability of Numerical Algorithms, SIAM Press, 2nd edition, 2003.
• L.. Granvilliers: An Interval Component for Continuous Constraints, Journal of Computational and Applied Mathematics, vol 162, no 1, pp. 79-92, 2004
  L. Granvilliers, E. Monfroy: Implementing Constraint Propagation by Composition of Reductions, Proceedings of the International Conference on Logic Programming, ICLP 2003, Springer LNCS 2916, pp. 300-314, 2003.
• J. Harrison: A Machine-Checked Theory of Floating Point Arithmetic, Proceedings of the 1999 International Conference on Theorem Proving in Higher Order Logics, TPHOLs'99. Springer LNCS 1690, pp. 113-130, 1999.
• T. Hickey: Analytic Constraint Solving and Interval Arithmetic, Proceedings of the 27th Annual ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL'00).
• T. Hickey, Q. Ju, M.H. van Emden: Interval Arithmetic: from Principles to Implementation, Journal of the ACM, volume 48, issue 5, pp. 1038-1068, September 2001.
• N. Higham: Exploiting Fast Matrix Multiplication Within the Level 3 BLAS, ACM Transactions on Mathematical Software, vol 16, no 4, pp 352-368, 1990.
• F. Jézéquel: Dynamical control of converging sequences computation, Applied Numerical Mathematics, vol 50, 2004, pp 147-164.
• Ph. Langlois: Automatic Linear Correction of Rounding Errors, BIT Numerical Mathematics, vol 41, no 3, 2001, pp 515-539.
• X.S. Li, J.W. Demmel, D.H. Bailey, G. Henry, Y.hida, J. Iskandar, W. Kahan, S.Y. Kang, A. Kapur, M.C. Marti, B.J. Thompson, T. Tung and D.J. Yoo: Design, Implementation and Testing of Extended and Mixed Precision BLAS, ACM Transactions on Mathematical Software, vol 28, no 2, 2002, pp 152-205.
• G. Melquiond, S. Pion: Formally Certified Floating-Point Filters for Homogeneous Geometric Predicates, to appear in Theoretical Informatics and Applications, 2007.
• D. Michelucci, J.-M. Moreau, S. Foufou: Robustness and Randomness, to appear in Lecture Notes in Computer Science, special issue on Reliable Implementation of Real Numbers Algorithms: Theory and Practice, 2007.
• Y. Nievergelt: Scalar fused multiply-add instructions produce floating-point matrix arithmetic provably accurate to the penultimate digit, ACM Transactions on Mathematical Software vol 29, no 1, 2003, pp 27-48.
• F. Rouillier, P. Zimmermann: Efficient isolation of polynomial's real roots, Journal of Computational and Applied Mathematics, vol 162, pp. 33-50, 2004.
• S.M. Rump, T. Ogita, and S. Oishi: Accurate Floating-Point Summation, Technical Report 05.1, Faculty of Information and Communication Science, Hamburg University of Technology, 2005. Available here.
• H. Schichl, A. Neumaier: Interval Analysis on Directed Acyclic Graphs for Global Optimization, Journal of Global Optimization, vol 33, pp.541-562, 2005.
• J.R. Shewchuk: Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates, Discrete Computational Geometry, vol 18, 1997, pp 305-363,
  except Section 2 which will be detailed during lecture 6.

Lecture notes (incomplete)

• Lecture 1
  • General introduction to this course: notes (in french)
  • Introduction to IEEE-754 floating-point arithmetic: floating-point numbers and their representation, rounding modes and ulps, special values (zeros, infinities, NaNs).
    Exercises: what does Gentleman's program do?, devise programs that spy the machine representation (length of the mantissa, extreme values for the exponents).
  
  
  
• Lecture 2: IEEE-754 floating-point arithmetic and condition number
  • Properties that can be established thanks to the IEEE-754 standard, TwoSum and TwoMult: notes
  • Work on the paper by T. Ogita, S.M. Rump and S. Oishi: Accurate Sum and Dot Product with Applications, Proceedings of 2004 IEEE International Symposium on Computer Aided Control Systems Design, Taipei, pages 152-155, 2004.
  • Condition number: intuition and definition
  
  
  
• Lecture 3: Error analysis
  • Condition number: notes
  • Stability of an algorithm: forward analysis, backward analysis, accuracy of the solution
  
  
  
  
• Lecture 4: Error analysis of some examples
  • JM Muller's recurrence, Let's count to 6 (N. Higham)...: notes
  • linear systems solving: triangular systems, LU factorization
  
  
  
• Lecture 5: Probabilistic arithmetic
  • CESTAC method
  • Monte Carlo arithmetic and Kahan's criticisms: notes
  
  
  
• Lecture 6: Multiple precision arithmetic notes
  • Expansions
  • Multiple precision arithmetic (based on integer computations)
  
  
  
  
• Lecture 7: Interval arithmetic: notes
  
  
• Lecture 8: Interval arithmetic
  
  
• Lecture 9: Exact arithmetic
  
  
• Lecture 10: Exact arithmetic
  
  
• Lecture 11: Formal proofs
  
  

Miscellaneous

Go to Page Teaching of Nathalie Revol
Go to Page Nathalie Revol
Go to Page Arenaire
Go to Page LIP
Go to Page INRIA Rhône-Alpes
Go to Page ANO
Go to Page USTL