Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Improved rounding for spline coefficients and knots

Authors: Eric Grosse and John D. Hobby
Journal: Math. Comp. 63 (1994), 175-194
MSC: Primary 65D07
MathSciNet review: 1240659
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: 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.

References [Enhancements On Off] (What's this?)

  • [1] L. Babai, On Lovász' lattice reduction and the nearest lattice point problem, Combinatorica 6 (1986), 1-13. MR 856638 (88a:68049)
  • [2] P. E. Bjørstad and E. H. Grosse, Conformal mapping of circular arc polygons, SIAM J. Sci. Statist. Comput. 8 (1987), 19-32. MR 873921 (88d:30010)
  • [3] C. de Boor, Good approximation by splines with variable knots. II, Numerical Solution of Differential Equations (G. A. Watson, ed.), Springer-Verlag, New York, 1974, pp. 12-20. MR 0431606 (55:4603)
  • [4] 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.
  • [5] 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.
  • [6] 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.
  • [7] D. L. B. Jupp, Approximation to data by splines with free knots, SIAM J. Numer. Anal. 15 (1978), 328-343. MR 488884 (81e:41011)
  • [8] J. C. Lagarias, H. W. Lenstra, Jr., and C. P. Schnorr, Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal, Combinatorica 10 (1990), 333-348. MR 1099248 (92a:11075)
  • [9] B. A. LaMacchia, Basis reduction algorithms and subset sum problems, Master's thesis, EECS Dept., Massachusetts Institute of Technology, 1991.
  • [10] A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), 515-534. MR 682664 (84a:12002)
  • [11] 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), 393-409. MR 1118964 (93b:65016)
  • [12] B. Meinardus, G. Nürnberger, M. Sommer, and H. Strauss, Algorithms for piecewise polynomials and splines with free knots, Math. Comp. 53 (1989), 235-247. MR 969492 (90d:65033)
  • [13] C. P. Schnorr, A hierarchy of polynomial time lattice basis reduction algorithms, Theoret. Comput. Sci. 53 (1987), 201-224. MR 918090 (89h:11085)
  • [14] -, A more efficient algorithm for lattice basis reduction, J. Algorithms 9 (1988), 47-62. MR 925597 (89h:11086)
  • [15] C. P. Schnorr and M. Euchner, Lattice basis reduction: Improved practical algorithms and solving subset sum problems, Proc. of Fundamentals of Comput. Theory '91, Lecture Notes in Comput. Sci., Springer-Verlag, New York, 1991. MR 1136071
  • [16] N. L. Schryer, SSAF-smooth spline approximations to functions, Technical report, AT&T Bell Laboratories CSTR 131, 1986.
  • [17] L. L. Schumaker, Spline functions: Basic theory, Wiley, New York, 1981. MR 606200 (82j:41001)
  • [18] TIGER/LINE census files, 1990, technical documentation, Technical report, Bureau of the Census, U. S. Dept. of Commerce, Washington, D.C., 1991.
  • [19] 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.
  • [20] 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

Keywords: Free-knot splines, parameterized splines, rounding, closest lattice point, compression
Article copyright: © Copyright 1994 American Mathematical Society

American Mathematical Society