Path: utzoo!attcan!uunet!mailrus!cs.utexas.edu!samsung!gem.mps.ohio-state.edu!pacific.mps.ohio-state.edu!tut.cis.ohio-state.edu!att!watmath!watcgl!rhbartels
From: rhbartels@watcgl.waterloo.edu (Richard Bartels)
Newsgroups: comp.graphics
Subject: Re: Spline coefficients
Keywords: matrix problem, help
Message-ID: <12349@watcgl.waterloo.edu>
Date: 19 Nov 89 22:19:25 GMT
References: <352@texhrc.UUCP>
Reply-To: rhbartels@watcgl.waterloo.edu (Richard Bartels)
Organization: U. of Waterloo, Ontario
Lines: 44

In article <352@texhrc.UUCP> bls@texhrc.UUCP (Brian L. Sumner) writes:
>
>I am tring to determine a set of spline coefficients, and to do
>so I need to solve the linear system
>    Ax = b
>where A can be a very large (positive definite?) banded matrix.
>
>[   ... description deleted ... ]
>

The description sounds suspiciously like the sort of matrix that arises
from interpolating or fitting over a rectilinear mesh (a tensor-product grid).
If this is the case, then deBoor's book, "A Practical Guide to Splines"
and the following two articles might be instructive.  Briefly, a tensor-product
problem in n dimensions can be reduced to n successive one-dimensional
problems.  With B-splines, a each one-dimensional problem interpolation
problem, for example, typically involves a k-banded matrix, where k is the
degree of the spline; e.g.,  cubics involve tridiagonal matrices.
Such systems can be solved in linear time.  deBoor's book offers code
(also available on NETLIB), and the articles show how the tensor-product
insight extends to least squares fitting (as well as being more readible
than the explanation given by deBoor).

-Richard
==========================================================================
%A P. Dierckx
%L Dierckx77-
%T An algorithm for least-squares fitting of cubic spline surfaces
to functions on a rectilinear mesh over a rectangle
%J Journal of Computational and Applied Mathematics
%V 3
%N 2
%D 1977
%P 113-129
%l journal-article

%A P. Dierckx
%L Dierckx81-
%T An Algorithm for Surface-Fitting with Spline Functions
%J IMA Journal of Numerical Analysis
%V 1
%D 1981
%P 267-283
%l journal-article