forked from xiaolongma/jburkardt-f
-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathsparse_interp_nd.html
284 lines (246 loc) · 9 KB
/
sparse_interp_nd.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
<html>
<head>
<title>
SPARSE_INTERP_ND - Multidimensional Sparse Interpolant
</title>
</head>
<body bgcolor="#EEEEEE" link="#CC0000" alink="#FF3300" vlink="#000055">
<h1 align = "center">
SPARSE_INTERP_ND <br> Multidimensional Sparse Interpolant
</h1>
<hr>
<p>
<b>SPARSE_INTERP_ND</b>
is a FORTRAN90 library which
can be used to construct a sparse interpolant to a function f(x) of
a multidimensional argument x.
</p>
<p>
The problem is defined as follows: for any point x in some M-dimensional
product space X, such as the unit hypercube, we are able to provide the
value f(x) for some function f(). We wish to determine a new function g(),
(the interpolant) which will match the value of f() on some specified set
of points {xi}. Presumably, we choose the number and location of the
points {xi} to ensure that the interpolating function g() is a good fit
to f().
</p>
<p>
There are standard techniques for producing a family of interpolants g(j)(),
such that, as we increase the index j, the interpolating process will exactly
match any function f() which happens to be a polynomial of limited degree.
The usual techniques for doing this are derived from tensor product interpolants,
whose expense grows exponentially with the spatial dimension.
</p>
<p>
For simplicity,
we'll assume that the argument space X is the unit hypercube, and that we
have a family of 1D interpolation rules g(j)(), where the index j is an indication
of the precision of the interpolation rule. A typical tensor product interpolant
G(J)() can then be thought of as constructed by the product
<pre>
G(J)(X) = g(j1)(x1) * g(j2)(x2) * ... * g(jm)(xm).
</pre>
where, of course, J = (j1,j2,...jm) and X = (x1,x2,...,xm).
</p>
<p>
A procedure due to Smolyak, which is more typically applied to problems in
quadrature, can also be used for the interpolation problem. The Smolyak
interpolation rule of level L is defined by
<pre>
A(L,M) = sum ( L-M+1 <= |J| <= L ) C(|J|) * g(j1)(x1) * g(j2)(x2) * ... * g(jm)(xm).
</pre>
Here |J| = j1+j2+...+jm, and, for each |J|, the sum must be taken over all
possible vectors J with nonnegative integer entries that sum to |J|.
</p>
<p>
Thus, a naive implementation of a sparse interpolant would, for a given spatial
dimension M, pick a level L, determine the (at most L+1) coefficients C(),
construct every tensor product interpolant of total degree L or less, evaluate
each interpolant at the point X, and combine these values with the appropriate
weights C() to arrive at the sparse grid interpolant value at X.
</p>
<p>
Some improvements to this approach can be suggested. First, many of the
coefficients C() may be zero, because the coefficient vector C for an
M-dimensional sparse interpolant of level L will have at most M nonzero coefficients.
Secondly, if the 1D interpolation family is chosen so that the interpolant points
of successive members are nested, then it is possible to simplify the evaluation
process greatly.
</p>
<p>
<b>SPARSE_INTERP_ND</b> also requires access to the R8LIB library.
</p>
<h3 align = "center">
Licensing:
</h3>
<p>
The computer code and data files described and made available on this
web page are distributed under
<a href = "../../txt/gnu_lgpl.txt">the GNU LGPL license.</a>
</p>
<h3 align = "center">
Languages:
</h3>
<p>
<b>SPARSE_INTERP_ND</b> is available in
<a href = "../../c_src/sparse_interp_nd/sparse_interp_nd.html">a C version</a> and
<a href = "../../cpp_src/sparse_interp_nd/sparse_interp_nd.html">a C++ version</a> and
<a href = "../../f77_src/sparse_interp_nd/sparse_interp_nd.html">a FORTRAN77 version</a> and
<a href = "../../f_src/sparse_interp_nd/sparse_interp_nd.html">a FORTRAN90 version</a> and
<a href = "../../m_src/sparse_interp_nd/sparse_interp_nd.html">a MATLAB version</a>.
</p>
<h3 align = "center">
Related Data and Programs:
</h3>
<p>
<a href = "../../f_src/lagrange_interp_nd/lagrange_interp_nd.html">
LAGRANGE_INTERP_ND</a>,
a FORTRAN90 library which
defines and evaluates the Lagrange polynomial p(x)
which interpolates a set of data depending on a multidimensional argument x
that was evaluated on a product grid, so that p(x(i)) = z(i).
</p>
<p>
<a href = "../../f_src/r8lib/r8lib.html">
R8LIB</a>,
a FORTRAN90 library which
contains many utility routines using double precision real (R8) arithmetic.
</p>
<p>
<a href = "../../f_src/rbf_interp_nd/rbf_interp_nd.html">
RBF_INTERP_ND</a>,
a FORTRAN90 library which
defines and evaluates radial basis interpolants to multidimensional data.
</p>
<p>
<a href = "../../f_src/shepard_interp_nd/shepard_interp_nd.html">
SHEPARD_INTERP_ND</a>,
a FORTRAN90 library which
defines and evaluates Shepard interpolants to multidimensional data,
based on inverse distance weighting.
</p>
<p>
<a href = "../../m_src/spinterp/spinterp.html">
SPINTERP</a>,
a MATLAB library which
carries out piecewise multilinear hierarchical sparse grid interpolation;
an earlier version of this software is ACM TOMS Algorithm 847,
by Andreas Klimke;
</p>
<p>
<a href = "../../f_src/test_interp_nd/test_interp_nd.html">
TEST_INTERP_ND</a>,
a FORTRAN90 library which
defines test problems for interpolation of data z(x),
depending on an M-dimensional argument.
</p>
<h3 align = "center">
Reference:
</h3>
<p>
<ol>
<li>
Volker Barthelmann, Erich Novak, Klaus Ritter,<br>
High Dimensional Polynomial Interpolation on Sparse Grids,<br>
Advances in Computational Mathematics,<br>
Volume 12, Number 4, 2000, pages 273-288.
</li>
<li>
Andreas Klimke, Barbara Wohlmuth,<br>
Algorithm 847:
SPINTERP: Piecewise Multilinear Hierarchical Sparse Grid
Interpolation in MATLAB,<br>
ACM Transactions on Mathematical Software,<br>
Volume 31, Number 4, December 2005, pages 561-579.
</li>
<li>
Sergey Smolyak,<br>
Quadrature and Interpolation Formulas for Tensor Products of
Certain Classes of Functions,<br>
Doklady Akademii Nauk SSSR,<br>
Volume 4, 1963, pages 240-243.
</li>
</ol>
</p>
<h3 align = "center">
Source Code:
</h3>
<p>
<ul>
<li>
<a href = "sparse_interp_nd.f90">sparse_interp_nd.f90</a>, the source code.
</li>
<li>
<a href = "sparse_interp_nd.sh">sparse_interp_nd.sh</a>,
BASH commands to compile the source code.
</li>
</ul>
</p>
<h3 align = "center">
Examples and Tests:
</h3>
<p>
<ul>
<li>
<a href = "sparse_interp_nd_prb.f90">sparse_interp_nd_prb.f90</a>,
a sample calling program.
</li>
<li>
<a href = "sparse_interp_nd_prb.sh">sparse_interp_nd_prb.sh</a>,
BASH commands to compile and run the sample program.
</li>
<li>
<a href = "sparse_interp_nd_prb_output.txt">sparse_interp_nd_prb_output.txt</a>,
the output file.
</li>
</ul>
</p>
<h3 align = "center">
List of Routines:
</h3>
<p>
<ul>
<li>
<b>CC_COMPUTE_POINTS:</b> abscissas of a Clenshaw Curtis rule.
</li>
<li>
<b>COMP_NEXT</b> computes the compositions of the integer N into K parts.
</li>
<li>
<b>I4_CHOOSE</b> computes the binomial coefficient C(N,K) as an I4.
</li>
<li>
<b>I4_MOP</b> returns the I-th power of -1 as an I4.
</li>
<li>
<b>LAGRANGE_BASIS_1D</b> evaluates a 1D Lagrange basis.
</li>
<li>
<b>LAGRANGE_INTERP_ND_GRID2</b> sets an M-dimensional Lagrange interpolant grid.
</li>
<li>
<b>LAGRANGE_INTERP_ND_SIZE2</b> sizes an M-dimensional Lagrange interpolant.
</li>
<li>
<b>LAGRANGE_INTERP_ND_VALUE2</b> evaluates an ND Lagrange interpolant.
</li>
<li>
<b>ORDER_FROM_LEVEL_135</b> evaluates the 135 level-to-order relationship.
</li>
<li>
<b>SMOLYAK_COEFFICIENTS</b> returns the Smolyak coefficients and counts.
</li>
</ul>
</p>
<p>
You can go up one level to <a href = "../f_src.html">
the FORTRAN90 source codes</a>.
</p>
<hr>
<i>
Last revised on 05 October 2012.
</i>
<!-- John Burkardt -->
</body>
<!-- Initial HTML skeleton created by HTMLINDEX. -->
</html>