Nathalie Revol's teaching: Master class "Validation in Scientific Computing", ENS Lyon, 2006-2007
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)
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.
Exam papers:
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.
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.