REU Numerical Analysis Project, Summer, 2006
What's 
- [11 Jul] Added Maple work sheet "elimination" to demonstrate use of elimination term order.
- [06 Jul] Matlab M-files EntPoly,ComparePoly,Basis1,Basis2 test Hermite quintic interpolation.
- [06 Jul] Maple work sheet "erk4d" exhibits 4th-order Runge-Kutta with doubling as 11-stage, 5th-order formula; finds normal forms of 6th-order truncation error terms.
- [05 Jul] Draft report revised, updated with table of 5th-order trees.
- [30 Jun] Matlab function M-file ode2d uses optimized 2nd-order Runge-Kutta with extrapolation, stepsize control.
- [30 Jun] Updated draft report with Error vs Effort graph.
- [29 Jun] Maple work sheet "erk2d" exhibits 2nd-order Runge-Kutta with doubling as a 5-stage, 3rd-order formula.
- [28 Jun] Maple work sheet "erk45", first version.
- [28 Jun] Revised Maple work sheet "Runge-Kutta" to Maple directory.
- [27 Jun] Added InterpN2 to matlab directory; updated RK44Auto.m. Added draft preliminary report to documents directory.
- [26 Jun] Added RK44Auto.m to matlab directory.
- [22 Jun] Added amsart.tpl to Documents directory.
- [16 Jun] Added TrapAuto.m to matlab directory.
- [15 Jun] Updated RK(3,3) worksheet in Maple directory, added "unit.mws" worksheet about determining units in Q[x]/<x^6-x^2>.
- [14 Jun] Added RK(4,4) worksheet to Maple directory.
- [13 Jun] Added exercise and explicit 3-stage Runge-Kutta worksheets to Maple directory.
- [12 Jun] Added Vandermonde solver vsolve to Maple directory
- [12 Jun] Added Runge-Kutta functions and scripts to Matlab directory
- [ 8 Jun] New documents and references added.
- [ 6 Jun] Matlab scripts: interpolate US population data, interpolation error.
- [5 Jun] Project Outline
To Do
- Search literature for work on use of Groebner bases in derivation of explicit Runge-Kutta formulas.
- Use an elimination term order to solve the equations for 7-stage FSAL explicit Runge-Kutta (4,5) pair having stage order vector [\inf,1,3,3,3,3,5].
- Choose a small battery of ODE test problems for comparing performance.
- Among extrapolated 4-stage 4th-order formulas find a minimizer of || T_6 ||^2 subject to \hat{T}_5 not too small and || \hat{T}_6-T_6|| / || \hat{T}_5 || not too large.
Done
- Prove: if k is a field then the polynomial ring k[x] is principal.
- Prove the formula for the determinant of a Van der Monde matrix.
- Prove: if I is an ideal of a ring R, and x,x',y,y' in R satisfy x=x' (mod I) and y=y' (mod I), then x+y=x'+y' (mod I).
- Derive a formula for the volume of n-simplex.
- Find the Taylor series for the solution of y'=Ay, y(0)=1 by differentiating the differential equation.
- Make a table of rooted trees of all orders up to five, showing their corresponding elementary differentials and their "factorials" and "alphas".
- Derive, with proof, a formula for the inverse of the Van der Monde matrix.
- Write a function M-file RK3FixH.m to integrate ODE's by a 3rd-order Runge-Kutta formula of your choice; write a script M-file ShowRK3.m to demonstrate its performance.
- Let R be a commutative ring with identity, I an ideal of R. Prove
- If I is a prime ideal, then the quotient ring R/I is a domain.
- If I is a maximal ideal, then the quotient ring R/I is a field.
- In Maple, set up coefficient arrays A,b,c for an explicit 4-stage Runge-Kutta formula.
The formula has order four if eight polynomial equations in the components of A,b,c are satisfied.
Choose a term-order, and find a Gröbner basis for the ideal generated by these eight polynomials.
- If R is a commutative ring with identity and a in R is irreducible, is the principal ideal <a> a prime ideal?
- Find a way to use a Gröbner basis for an ideal I of R=k[x_1,...,x_n] to determine whether f in R/I is invertible.
- RK(4,4): Experiment with choices of nodes c_2,c_3 that make selected 5th order truncation error coefficients zero.
- When the 5th-order truncation error coefficients of a RK(4,4) formula are reduced modulo the ideal of 4th-order error conditions, there are four pairs whose elements are constant multiples of each other. Is there a relationship between the corresponding trees?
- What is the correspondence between prime ideals in k[x_1,...,x_n] and irreducible affine varieties in k^n? Between maximal ideals in k[x_1,...,x_n] and one-point affine varieties in k^n?
- Draft a LaTeX outline for a report on RK(4,4) formulas.
- Search the textbook and published literature for optimized RK(4,4) formulas.
- How does a sum of b_i*(c_i)^s reduce mod the ideal generated by the quadrature conditions sum_{i=1}^s b_i*(c_i)^(k-1)=1/k, k=1..s?
- Find criteria for an ideal in k[x_1,...,x_n] to be prime or maximal.
- Create and test a Matlab function M-file rk44.m implementing a RK(4,4) formula with step-doubling.
- Search among RK(4,4) formulas depending on c_2,c_3 for a minimizer of the sum of squares or the maximum of 5th-order truncation error coefficients.
- Derive RK(4,4) formulas with c_2=1/2 or c_2=c_3 (or both).
- Draft Introduction section of Preliminary Report.
- Draft RK(4,4) section of Preliminary Report.
- Revise RK44Auto to report performance statistics; compare different formulas with each other and with Matlab's ode45 on the orbitode problem.
- Find normal forms of 6th-order truncation error terms for 4th-order Runge-Kutta with doubling and extrapolation.
Lessons
Numerical analysis
- Polynomial Interpolation
- Van der Monde
- Lagrange
- Newton
- Hermite-Genocchi formula; error analysis
- Derivatives and integrals by interpolation
- Solution of differential equations by Taylor series
- Runge-Kutta formulas, Taylor expansion of Runge-Kutta solution, order conditions
- Error estimation by step-doubling
- Error estimation by embedding (Fehlberg's scheme)
- Simplifying conditions and subquadratures
Algebra
- Ring, homomorphism, ideal, quotient ring, prime and maximal ideals
- Noetherian ring, Hilbert basis theorem
- Polynomial roots and factors, elementary symmetric polynomials
- Groebner basis
- Varieties and ideals
- Elimination term orders
Topics and References
- Scientific Writing Links
- Power Point is Evil
- Classification of plane autonomous linear systems. Olver and Shakiban. (The author's web site for the book has a basic introduction to Matlab.)
- Numerical methods for ordinary differential systems: the initial value problem, Lambert.
- A First Course in Abstract Algebra, Rotman.
- Elementary Numerical Analysis, Conte & deBoor.
- Accuracy and Stability of Numerical Algorithms, Higham.
- Numerical ODE methods, Shampine.
- Runge-Kutta Methods, Trees and Maple, Bornemann.
- Matlab ODE solvers. Shampine, L. F. and M. W. Reichelt, "The MATLAB ODE Suite," SIAM Journal on Scientific Computing, Vol. 18, 1997, pp 1-22: [PostScript] [Acrobat].
Tasks
Documents