Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

ISSN 1088-6842 (online) ISSN 0025-5718 (print)

The 2020 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.


Improved rounding for spline coefficients and knots
HTML articles powered by AMS MathViewer

by Eric Grosse and John D. Hobby PDF
Math. Comp. 63 (1994), 175-194 Request permission


When representing the coefficients and knots of a spline using only small integers, independently rounding each infinite-precision value is not the best strategy. We show how to build an affine model for the error expanded about the optimal full-precision free-knot or parameterized spline, then use the Lovász basis reduction algorithm to select a better rounding. The technique could be used for other situations in which a quadratic error model can be computed.
  • L. Babai, On Lovász’ lattice reduction and the nearest lattice point problem, Combinatorica 6 (1986), no. 1, 1–13. MR 856638, DOI 10.1007/BF02579403
  • Petter Bjørstad and Eric Grosse, Conformal mapping of circular arc polygons, SIAM J. Sci. Statist. Comput. 8 (1987), no. 1, 19–32. MR 873921, DOI 10.1137/0908003
  • Carl de Boor, Good approximation by splines with variable knots. II, Conference on the Numerical Solution of Differential Equations (Univ. Dundee, Dundee, 1973) Lecture Notes in Math., Vol. 363, Springer, Berlin, 1974, pp. 12–20. MR 0431606
  • C. de Boor and J. R. Rice, Least squares cubic spline approximation. II: variable knots, Technical report, CSD TR 21, Purdue Univ., Lafayette, IN, 1968. J. E. Dennis, Jr., D. M. Gay, and R. E. Welch, An adaptive nonlinear least squares algorithm, ACM Trans. Math. Software 7 (1981), 348-368, 369-383. F. N. Fritsch and G. M. Nielson, On the problem of determining the distance between parametric curves, Technical report, Lawrence Livermore National Laboratory UCRL-JC-105408, 1990.
  • David L. B. Jupp, Approximation to data by splines with free knots, SIAM J. Numer. Anal. 15 (1978), no. 2, 328–343. MR 488884, DOI 10.1137/0715022
  • J. C. Lagarias, H. W. Lenstra Jr., and C.-P. Schnorr, Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice, Combinatorica 10 (1990), no. 4, 333–348. MR 1099248, DOI 10.1007/BF02128669
  • B. A. LaMacchia, Basis reduction algorithms and subset sum problems, Master’s thesis, EECS Dept., Massachusetts Institute of Technology, 1991.
  • A. K. Lenstra, H. W. Lenstra Jr., and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), no. 4, 515–534. MR 682664, DOI 10.1007/BF01457454
  • P. D. Loach and A. J. Wathen, On the best least squares approximation of continuous functions using linear splines with free knots, IMA J. Numer. Anal. 11 (1991), no. 3, 393–409. MR 1118964, DOI 10.1093/imanum/11.3.393
  • G. Meinardus, G. Nürnberger, M. Sommer, and H. Strauss, Algorithms for piecewise polynomials and splines with free knots, Math. Comp. 53 (1989), no. 187, 235–247. MR 969492, DOI 10.1090/S0025-5718-1989-0969492-7
  • C.-P. Schnorr, A hierarchy of polynomial time lattice basis reduction algorithms, Theoret. Comput. Sci. 53 (1987), no. 2-3, 201–224. MR 918090, DOI 10.1016/0304-3975(87)90064-8
  • C.-P. Schnorr, A more efficient algorithm for lattice basis reduction, J. Algorithms 9 (1988), no. 1, 47–62. MR 925597, DOI 10.1016/0196-6774(88)90004-1
  • C.-P. Schnorr and M. Euchner, Lattice basis reduction: improved practical algorithms and solving subset sum problems, Fundamentals of computation theory (Gosen, 1991) Lecture Notes in Comput. Sci., vol. 529, Springer, Berlin, 1991, pp. 68–85. MR 1136071, DOI 10.1007/3-540-54458-5_{5}1
  • N. L. Schryer, SSAF-smooth spline approximations to functions, Technical report, AT&T Bell Laboratories CSTR 131, 1986.
  • Larry L. Schumaker, Spline functions: basic theory, Pure and Applied Mathematics, John Wiley & Sons, Inc., New York, 1981. MR 606200
  • TIGER/LINE census files, 1990, technical documentation, Technical report, Bureau of the Census, U. S. Dept. of Commerce, Washington, D.C., 1991. P. van Emde Boas, Another NP-complete partition problem and the complexity of computing short vectors in a lattice, Report 81-04, Math. Institute, Univ. of Amsterdam, 1981. K. Wall and P.-E. Danielsson, A fast sequential method for polygonal approximation of digitized curves, Computer Vision, Graphics, and Image Processing, vol. 28, 1984, pp. 220-227.
Similar Articles
  • Retrieve articles in Mathematics of Computation with MSC: 65D07
  • Retrieve articles in all journals with MSC: 65D07
Additional Information
  • © Copyright 1994 American Mathematical Society
  • Journal: Math. Comp. 63 (1994), 175-194
  • MSC: Primary 65D07
  • DOI:
  • MathSciNet review: 1240659