Improved rounding for spline coefficients and knots

Grosse, Eric; Hobby, John D.

doi:10.1090/S0025-5718-1994-1240659-8

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

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

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

Least squares cubic spline approximation

variable knots

An adaptive nonlinear least squares algorithm

7

On the problem of determining the distance between parametric curves

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

Basis reduction algorithms and subset sum problems

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

SSAF-smooth spline approximations to functions

Larry L. Schumaker, Spline functions: basic theory, Pure and Applied Mathematics, John Wiley & Sons, Inc., New York, 1981. MR 606200

TIGER/LINE census files

technical documentation

Another NP-complete partition problem and the complexity of computing short vectors in a lattice

A fast sequential method for polygonal approximation of digitized curves