-
Notifications
You must be signed in to change notification settings - Fork 57
/
Copy pathsmolyak_display.html
420 lines (374 loc) · 13.4 KB
/
smolyak_display.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
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
<html>
<head>
<title>
SMOLYAK_DISPLAY - Display Smolyak Sparse Grid Construction
</title>
</head>
<body bgcolor="#EEEEEE" link="#CC0000" alink="#FF3300" vlink="#000055">
<h1 align = "center">
SMOLYAK_DISPLAY <br>
Display Smolyak Sparse Grid Construction
</h1>
<hr>
<p>
<b>SMOLYAK_DISPLAY</b>
is a MATLAB program which
displays the exactness diagram for a 2D Smolyak sparse grid,
by displaying and summing the exactness diagrams for the
component product rules.
</p>
<p>
The exactness diagram is a plot of the monomials <b>x^i y^j</b>
which are exactly integrated by the sparse grid. The sparse grid
"inherits" its exactness from the product rules that compose it,
and the program shows how this is done.
</p>
<p>
In 1D, a quadrature rule Q() is a list of N points X and weights W
which approximates an integral I(f) over some region by
<pre>
I(f) is approximated by Q(f) = sum ( 1 <= i <= n ) w(i) * f(x(i))
</pre>
</p>
<p>
In 2D (or higher), a product quadrature rule is the most common method
for estimating integrals in this way.
A product rule in 2D is formed by taking two rules for 1D
quadrature, say Q1 and Q2, and forming the rule Q = Q1 x Q2.
Here, the points of the rule Q are formed by taking all possible
pairs (x1,x2), with weights w1*w2.
</p>
<p>
A Smolyak sparse grid is generally used to form a quadrature
rule Q(f) to approximate the integral I(f) of a multivariate
function f(x) over a domain that is a product region. Although
Smolyak grids are related to product rules, they generally are
able to produce accurate estimates at a much lower "cost",
that is, with a much smaller number of points N.
</p>
<p>
Typically, for a given spatial dimension D, Smolyak sparse grids
are available in a sequence of sizes called "levels". Level 0
is a single point rule, and subsequent levels add more points and
more accurate integral estimates.
</p>
<p>
In 2D, a Smolyak grid is a combination created by adding together
product rules of a given product level, and subtracting product
rules of the previous level.
</p>
<p>
One way to analyze the behavior of a sequence of sparse grids is to
investigate their exactness.
</p>
<p>
A quadrature rule is exact for an integrand <b>f(x)</b>
if it is true that <b>Q(f)=I(f)</b>. Typically, for a 1D quadrature
rule, we are interested in the exactness for monomials of the
form <b>x^j</b>, and a quadrature rule has exactness up to degree
<b>k</b> if it is exact for all monomials from <b>x^0</b> through
<b>x^k</b>. This immediately implies that the quadrature rule
will be exact for any polynomial of degree <b>k</b> or less, and
hence is strong information about the approximation ability of the rule.
</p>
<p>
An exactness diagram for a quadrature rule can be made, which displays
all the monomials which the rule can integrate exactly. Since we
are considering a Smolyak sparse grid, we can display the evolution
of the exactness diagram, as we add or subtract each component
product grid to the sparse grid. The program draws a black diagonal
line to mark the total degree exactness of the sparse grid. It shows
in dark blue the monomials which can be exactly integrated by the rule,
and which lie below the exactness line. Light blue is used for monomials
that can be integrated exactly, but which lie above the exactness line;
these represent, in some sense, superfluous accuracy. Until the sparse
grid is completely constructed, some monomials under the exactness line
may actually be incorrectly estimated at double, or triple, or minus
their true value. This is suggested by using other colors for such
monomials. However, once the sparse grid is complete, the entire
field of monomials below the diagonal line should be dark blue.
</p>
<p>
Two "families" of quadrature rules are available:
</p>
<p>
The Clenshaw-Curtis
family is defined on [-1,+1]. Roughly speaking, the rule with N points
has exactness N-1. Actually, because of symmetric, if N is odd, then
the rule with N points will actually have exactness N. In particular,
the rule with 1 point has exactness 1, and can integrate both constants
(degree 0) and linear functions (degree 1) exactly.
</p>
<p>
The Legendre family is defined on [-1,+1]. The rule with N points
has exactness 2*N-1.
</p>
<p>
While the families can produce rules of any size, we wish to select
a subsequence of these rules, which increase in size to satisfy
some pattern we specify. This pattern is called the "growth rate".
A common growth rate is "exponential", in which the number of points
roughly doubles on each step. For technical reasons, the Clenshaw-Curtis
and Legendre families differ in how they grow exponentially. Other
simple growth rules include "slow exponential", "linear", and "linear odd".
</p>
<p>
The "hyperbolic cross" growth rule is quite different from the others.
Essentially, when we specify a level L, the 2D product rules that we will
be combining for the hyperbolic cross involve sizes L1 and L2 whose
product is L (or close to it). Thus, the hyperbolic cross grid of
level 5 adds: +Q(1)xQ(6) + Q(2)xQ(3) + Q(3)xQ(2) + Q(6)xQ(1)
and subtracts: -Q(1)xQ(3)-Q(2)xQ(2)-Q(3)xQ(1). This growth rule is
appropriate for integrand functions which are biases towards pure
powers of a single variable (x or y in our case) and against powers
that involve both x and y.
</p>
<h3 align = "center">
Usage:
</h3>
<p>
<blockquote>
<b>smolyak_display</b> ( <i>'family'</i>, <i>'growth'</i>, <i>level</i> )
</blockquote>
where
<ul>
<li>
<i>'family'</i> is the name of the family of rules, in quotes.
</li>
<li>
<i>'growth'</i> is the growth rate, in quotes.
</li>
<li>
<i>level</i> is the level, between 0 and 5.
</li>
</ul>
</p>
<p>
Choices for <i>'family'</i> include:
<ul>
<li>
<i>'CC'</i>, the Clenshaw Curtis family of rules in [-1,+1];
</li>
<li>
<i>'L'</i>, the Gauss-Legendre family of rules in [-1,+1];
</li>
</ul>
</p>
<p>
Choices for <i>'growth'</i> include:
<ul>
<li>
<i>'E'</i> exponential growth; for 'CC', this selects rules
of order 1, 3, 5, 9, 17, 33, 65, ...; for 'L', this selects
rules of order 1, 3, 7, 15, 31, 63, ...;
</li>
<li>
<i>'HC'</i> hyperbolic cross; for both 'CC' and 'L', we have
available all the rules of order 1, 2, 3, 4, ... and combine
them as necessary.
</li>
<li>
<i>'L'</i> linear growth; for 'CC', this selects rules of order
1, 3, 5, 7, 9, ...; for 'L, this selects rules of order 1, 2, 3, 4, 5, ...;
</li>
<li>
<i>'LO'</i> linear odd growth; for 'CC', this is the same as the
linear growth; for 'L, this selects rules of order 1, 3, 3, 5, 5, 7, 7, ...;
</li>
<li>
<i>'SE'</i>, slow exponential growth, chooses a rule from the
exponential growth rate that is the smallest order that still
is "exact enough" for the sparse grid constraint;
</li>
</ul>
</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>SMOLYAK_DISPLAY</b> is available in
<a href = "../../m_src/smolyak_display/smolyak_display.html">a MATLAB version</a>.
</p>
<h3 align = "center">
Related Data and Programs:
</h3>
<p>
<a href = "../../c_src/smolpack/smolpack.html">
SMOLPACK</a>,
a C library which
estimates the integral of a function
over a M-dimensional hypercube using a sparse grid,
by Knut Petras;
</p>
<p>
<a href = "../../m_src/sparse_grid_hw/sparse_grid_hw.html">
SPARSE_GRID_HW</a>,
a MATLAB library which
creates sparse grids based on Gauss-Legendre, Gauss-Hermite,
Gauss-Patterson, or a nested variation of Gauss-Hermite rules,
by Florian Heiss and Viktor Winschel.
</p>
<p>
<a href = "../../m_src/spinterp/spinterp.html">
SPINTERP</a>,
a MATLAB library which
carries out piecewise multilinear
hierarchical sparse grid interpolation, quadrature and optimization,
by Andreas Klimke;
an earlier version of this software is ACM TOMS Algorithm 847.
</p>
<p>
<a href = "../../m_src/tsg/tsg.html">
TSG</a>,
a MATLAB library which
demonstrate the use of the TasmanianSparseGrid package,
which implements routines for working with sparse grids,
to efficiently estimate integrals or compute interpolants of
scalar functions of multidimensional arguments. The MATLAB
version is an interface to the C++ library,
by Miroslav Stoyanov.
</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>
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 = "exactness_1d.m">exactness_1d.m</a>
returns the exactness of a 1D quadrature rule,
given the family, growth, and level.
</li>
<li>
<a href = "order_1d.m">order_1d.m</a>
returns the order (number of points) in a 1D quadrature rule,
given the family, growth, and level.
</li>
<li>
<a href = "smolyak_display.m">smolyak_display.m</a>
displays the exactness diagram for a Smolyak grid of
given family, growth and level, by adding or subtracting
the exactness diagrams of the component product rules.
</li>
</ul>
</p>
<h3 align = "center">
Examples and Tests:
</h3>
<p>
<b>CC_E_3</b> displays the exactness diagrams for a sparse
grid of the CC family, with exponential growth, at sparse grid level 3.
<ul>
<li>
<a href = "cc_e_3_-0x2.png">cc_e_3_-0x2.png</a>
subtract Q0xQ2.
</li>
<li>
<a href = "cc_e_3_-1x1.png">cc_e_3_-1x1.png</a>
subtract Q1xQ1.
</li>
<li>
<a href = "cc_e_3_-2x0.png">cc_e_3_-2x0.png</a>
subtract Q2xQ0.
</li>
<li>
<a href = "cc_e_3_+0x3.png">cc_e_3_+0x3.png</a>
add Q0xQ3.
</li>
<li>
<a href = "cc_e_3_+1x2.png">cc_e_3_+1x2.png</a>
add Q1xQ2.
</li>
<li>
<a href = "cc_e_3_+2x1.png">cc_e_3_+2x1.png</a>
add Q2xQ1.
</li>
<li>
<a href = "cc_e_3_+3x0.png">cc_e_3_+3x0.png</a>
add Q3xQ0. This produces the final exactness diagram for the
full sparse grid.
</li>
</ul>
</p>
<p>
<b>CC_E_4</b> displays the exactness diagrams for a sparse
grid of the CC family, with exponential growth, at sparse grid level 4.
<ul>
<li>
<a href = "cc_e_4_-0x3.png">cc_e_4_-0x3.png</a>
subtract Q0xQ3.
</li>
<li>
<a href = "cc_e_4_-1x2.png">cc_e_4_-1x2.png</a>
subtract Q1xQ2.
</li>
<li>
<a href = "cc_e_4_-2x1.png">cc_e_4_-2x1.png</a>
subtract Q2xQ1.
</li>
<li>
<a href = "cc_e_4_-3x0.png">cc_e_4_-3x0.png</a>
subtract Q3xQ0.
</li>
<li>
<a href = "cc_e_4_+0x4.png">cc_e_4_+0x4.png</a>
add Q0xQ4.
</li>
<li>
<a href = "cc_e_4_+1x3.png">cc_e_4_+1x3.png</a>
add Q1xQ3.
</li>
<li>
<a href = "cc_e_4_+2x2.png">cc_e_4_+2x2.png</a>
add Q2xQ2.
</li>
<li>
<a href = "cc_e_4_+3x1.png">cc_e_4_+3x1.png</a>
add Q3xQ1.
</li>
<li>
<a href = "cc_e_4_+4x0.png">cc_e_4_+4x0.png</a>
add Q4xQ0. This produces the final exactness diagram for the
full sparse grid.
</li>
</ul>
</p>
<p>
You can go up one level to <a href = "../m_src.html">
the MATLAB source codes</a>.
</p>
<hr>
<i>
Last revised on 06 March 2014.
</i>
<!-- John Burkardt -->
</body>
<!-- Initial HTML skeleton created by HTMLINDEX. -->
</html>