Peter Alfeld Department of Mathematics College of Science University of Utah
The Bernstein Bézier Form Home Page Examples
Spline Spaces and Minimal Determining Sets    User's Guide Residual Arithmetic
Triangulations How does it work?    Bibliography


Dimensions on the Morgan-Scott Split

The Morgan-Scott Split is one of the most studied triangulations in multivariate spline theory since it exhibits a large number of varied phenomena. On this page we give the dimension of various configurations of the split, to illustrate the complexity of the split, and also to demonstrate the power of the MDS code. The dimensions can be obtained by running the code with a sufficiently high amount of memory. For example, the entries in the row r=13, d=27 were computed using 400 Mbytes of memory (and taking about 12 hours of CPU time on a Sparc 2 station).

As illustrated in the nearby figure, the Morgan split is obtained by taking a triangle with vertices V 0, V 1, V 2. inscribing another triangle with vertices V 3, V 4, V 5 . and adding edges to make a triangulation with seven triangles. It can also be obtained by projecting an octahedron into the plane (where the original triangle forms the image of the eight face of the octahedron).

The MDS code has several versions of the Morgan-Scott split on the list of built-in triangulations. In these illustrations we consider eight different configurations. Emphasis is on parallel pairs of edges emanating from the same vertex since they tend to cause dimensions to become non-generic. Note that for the effects to occur the edges must be exactly parallel which is possible to obtain because the coordinates of vertices are all integer.

For each configuration the following information is given:

Example 1: A generic configuration.

This configuration contains no recognized geometric artifacts. In all cases the dimension equals the generic value.

Example 2: One parallel pair of edges.

This configuration contains just one pair of parallel edges.

Example 3: Two parallel pairs of edges.

This configuration contains pairs of parallel edges. However, these do not form a singular vertex.

Example 4: A singular Vertex

This configuration contains two pairs of parallel edges which intersect to from a singular vertex.

Example 5: Three pairs of parallel edges.

This configuration contains three pairs of parallel edges. It has been used by Wang to construct a finite element.

Example 6: The symmetric Split.

This configuration is symmetric in the sense defined by Diener and discussed here.

Example 7: A partially symmetric split.

This configuration has vertices V 4 and V 5 symmetrically placed with respect to the line from V 0 V 3. Thus is exhibits part of Diener's symmetry.

Example 8: Diener's Example.

This strange looking configuration was given by Diener as an example of a configuration that satisfies an algebraic condition that came up in his analysis. It is reproduced as Diener gave, it with two of the edges of the inner triangle defined by the unit vectors in the plane.

Dimensions

The following table gives dimension of various spline spaces on the above described configurations. For each case, the true dimension is computed and compared to Schumaker's lower bound (for that particular configuration). When the dimension and the lower bound agree, their common value is listed. If they disagree, the dimension is listed, followed by a slash, and the discrepancy. Thus, for example, the dimension on the symmetric split when r=1 and d=2 is 7 and the lower bound is 6.

m and n are the dimension of the linear system that must be analyzed. They are included to illustrate the capacity of the MDS code.

For clarity, r and d are listed on a yellow background, and the matrix dimensions on a purple background. A cyan background indicates that the dimension of the spline space actually equals the dimension of the space of polynomials of degree d. Thus in that case all splines are in fact polynomials. A green background indicates that there are nontrivial splines, and the true dimension exceeds Schumaker's lower bound.

At present, except in the special case of the symmetric split and d=2r, we have no theory that explains the entries on a green background (except for configuration 8 in the case that d=2r, see Dwight Diener, Instability in the dimension of spaces of bivariate piecewise polynomials of degree 2r and smoothness order r. SIMA J. Numer. Anal., 27 (1990), pp. 543-551)

The dimension on the Morgan-split is completely understood (in the sense that we know a minimal determining set) in the case that d>3r+1. However, for the range of r considered here, discrepancies only occur for d< 2r+1. It is an open question whether discrepancies occur for larger of values of d, either on the Morgan-Scott split for values of r not considered here, or on configurations other than the Morgan-Scott split.

For r>11 the dimensions were computed twice, once modulo p = 231-1=2,147,483,647, and once modulo p = 231-17=2,147,483,629. The computed dimensions were identical, increasing one' confidence in the results of residual arithmetic.

The figures for r=13 were computed using 500 Mbytes of memory and took about 3 days of CPU time.

r d Conf. 1 Conf. 2 Conf. 3 Conf. 4 Conf. 5 Conf. 6 Conf. 7 Conf. 8 m n
                       
1 2 6 6 6 7 6 7 / 1 7 / 1 6 18 18
1 3 16 16 16 17 16 16 16 16 27 37
                       
2 3 10 / 3 10 / 2 10 / 1 10 / 1 10 10 / 3 10 / 3 10 / 3 45 37
2 4 15 16 17 18 18 16 / 1 16 / 1 16 / 1 63 63
2 5 30 31 32 33 33 30 30 30 81 96
                       
3 4 15 / 3 15 / 2 15 / 1 15 / 1 15 15 / 3 15 / 3 15 / 3 81 63
3 5 21 / 3 21 / 2 21 / 1 22 21 21 / 3 21 / 3 21 / 3 108 96
3 6 31 32 33 36 34 32 / 1 32 / 1 31 135 136
3 7 51 52 53 56 54 51 51 51 162 183
                       
4 5 21 / 3 21 / 2 21 / 1 21 / 1 21 21 / 3 21 / 3 21 / 3 126 96
4 6 28 / 6 28 / 4 28 / 2 28 / 1 28 28 / 6 28 / 6 28 / 6 162 136
4 7 36 / 3 37 / 2 38 / 1 40 39 37 / 4 37 / 4 36 / 3 198 183
4 8 51 53 55 59 57 52 / 1 52 / 1 51 234 237
4 9 76 78 80 84 82 76 76 76 270 298
                       
5 6 28 / 3 28 / 2 28 / 1 28 / 1 28 28 / 3 28 / 3 28 / 3 180 136
5 7 36 / 9 36 / 6 36 / 3 36 / 3 36 36 / 9 36 / 9 36 / 9 225 183
5 8 45 / 9 45 / 6 45 / 3 46 / 1 45 45 / 9 45 / 9 45 / 9 270 237
5 9 55 / 3 57 / 2 59 / 1 63 61 56 / 4 56 / 4 55 / 3 315 298
5 10 75 78 81 87 84 76 / 1 76 / 1 75 360 366
5 11 105 108 111 117 114 105 105 105 405 441
                       
6 7 36 / 3 36 / 2 36 / 1 36 / 1 36 36 / 3 36 / 3 36 / 3 243 183
6 8 45 / 9 45 / 6 45 / 3 45 / 3 45 45 / 9 45 / 9 45 / 9 297 237
6 9 55 / 12 55 / 8 55 / 4 55 / 2 55 55 / 12 55 / 12 55 / 12 351 298
6 10 66 / 9 67 / 6 68 / 3 70 69 66 / 9 66 / 9 66 / 9 405 366
6 11 78 82 86 93 90 82 / 4 82 / 4 78 459 441
6 12 106 110 114 122 118 107 / 1 107 / 1 106 513 523
6 13 141 145 149 157 153 141 141 141 567 612
                       
7 8 45 / 3 45 / 2 45 / 1 45 / 1 45 45 / 3 45 / 3 45 / 3 315 237
7 9 55 / 9 55 / 6 55 / 3 55 / 3 55 55 / 9 55 / 9 55 / 9 378 298
7 10 66 / 15 66 / 10 66 / 5 66 / 4 66 66 / 15 66 / 15 66 / 15 441 366
7 11 78 / 15 78 / 10 78 / 5 79 / 1 78 78 / 15 78 / 15 78 / 15 504 441
7 12 91 / 9 93 / 6 95 / 3 100 97 92 / 10 92 / 10 91 / 9 567 523
7 13 108 113 118 128 123 112 / 4 112 / 4 108 630 612
7 14 141 146 151 162 156 142 / 1 142 / 1 141 693 708
7 15 181 186 191 202 196 181 181 181 756 811
                       
8 9 55 / 3 55 / 2 55 / 1 55 / 1 55 55 / 3 55 / 3 55 / 3 396 298
8 10 66 / 9 66 / 6 66 / 3 66 / 3 66 66 / 9 66 / 9 66 / 9 468 366
8 11 78 / 18 78 / 12 78 / 6 78 / 6 78 78 / 18 78 / 18 78 / 18 540 441
8 12 91 / 21 91 / 14 91 / 7 91 / 4 91 91 / 21 91 / 21 91 / 21 612 523
8 13 105 / 18 106 / 12 107 / 6 109 / 1 108 105 / 18 105 / 18 105 / 18 684 612
8 14 120 / 9 124 / 6 128 / 3 135 132 121 / 10 121 / 10 120 / 9 756 708
8 15 142 149 156 168 163 146 / 4 146 / 4 142 828 811
8 16 180 187 194 207 201 181 / 1 181 / 1 180 900 921
8 17 225 232 239 252 246 225 225 225 972 1038
                       
9 10 66 / 3 66 / 2 66 / 1 66 / 1 66 66 / 3 66 / 3 66 / 3 486 366
9 11 78 / 9 78 / 6 78 / 3 78 / 3 78 78 / 9 78 / 9 78 / 9 567 441
9 12 91 / 18 91 / 12 91 / 6 91 / 6 91 91 / 18 91 / 18 91 / 18 648 523
9 13 105 / 24 105 / 16 105 / 8 105 / 6 105 105 / 24 105 / 24 105 / 24 729 612
9 14 120 / 24 120 / 16 120 / 8 121 / 2 120 120 / 24 120 / 24 120 / 24 810 708
9 15 136 / 18 138 / 12 140 / 6 145 142 136 / 18 136 / 18 136 / 18 891 811
9 16 153 / 6 159 / 4 165 / 2 177 171 157 / 10 157 / 10 153 / 6 972 921
9 17 183 191 199 215 207 187 / 4 187 / 4 183 1053 1038
9 18 226 234 242 259 250 227 / 1 227 / 1 226 1134 1162
9 19 276 284 292 309 300 276 276 276 1215 1293
                     
10 11 78 / 3 78 / 2 78 / 1 78 / 1 78 78 / 3 78 / 3 78 / 3 585 441
10 12 91 / 9 91 / 6 91 / 3 91 / 3 91 91 / 9 91 / 9 91 / 9 675 523
10 13 105 / 18 105 / 12 105 / 6 105 / 6 105 105 / 18 105 / 18 105 / 18 765 612
10 14 120 / 27 120 / 18 120 / 9 120 / 8 120 120 / 27 120 / 27 120 / 27 855 708
10 15 136 / 30 136 / 20 136 / 10 136 / 5 136 136 / 30 136 / 30 136 / 30 945 811
10 16 153 / 27 154 / 18 155 / 9 157 / 1 156 153 / 27 153 / 27 153 / 27 1035 921
10 17 171 / 18 175 / 12 179 / 6 187 183 172 / 19 172 / 19 171 / 18 1125 1038
10 18 190 / 3 199 / 2 208 / 1 224 217 197 / 10 197 / 10 190 / 3 1215 1162
10 19 228 238 248 267 258 232 / 4 232 / 4 228 1305 1293
10 20 276 286 296 316 306 277 / 1 277 / 1 276 1395 1431
10 21 331 341 351 371 361 331 331 331 1485 1576
                       
11 12 91 / 3 91 / 2 91 / 1 91 / 1 91 91 / 3 91 / 3 91 / 3 693 523
11 13 105 / 9 105 / 6 105 / 3 105 / 3 105 105 / 9 105 / 9 105 / 9 792 612
11 14 120 / 18 120 / 12 120 / 6 120 / 6 120 120 / 18 120 / 18 120 / 18 891 708
11 15 136 / 30 136 / 20 136 / 10 136 / 10 136 136 / 30 136 / 30 136 / 30 990 811
11 16 153 / 36 153 / 24 153 / 12 153 / 9 153 153 / 36 153 / 36 153 / 36 1089 921
11 17 171 / 36 171 / 24 171 / 12 172 / 4 171 171 / 36 171 / 36 171 / 36 1188 1038
11 18 190 / 30 192 / 20 194 / 10 199 / 1 196 190 / 30 190 / 30 190 / 30 1287 1162
11 19 210 / 18 216 / 12 222 / 6 234 228 211 / 19 211 / 19 210 / 18 1386 1293
11 20 231 244 / 1 256 / 1 276 267 241 / 10 241 / 10 231 1485 1431
11 21 277 289 301 324 313 281 / 4 281 / 4 277 1584 1576
11 22 330 342 354 378 366 331 / 1 331 / 1 330 1683 1728
11 23 390 402 414 438 426 390 390 390 1782 1887
                       
12 13 105 / 3 105 / 2 105 / 1 105 / 1 105 105 / 3 105 / 3 105 / 3 810 612
12 14 120 / 9 120 / 6 120 / 3 120 / 3 120 120 / 9 120 / 9 120 / 9 918 708
12 15 136 / 18 136 / 12 136 / 6 136 / 6 136 136 / 18 136 / 18 136 / 18 1026 811
12 16 153 / 30 153 / 20 153 / 10 153 / 10 153 153 / 30 153 / 30 153 / 30 1134 921
12 17 171 / 39 171 / 26 171 / 13 171 / 11 171 171 / 39 171 / 39 171 / 39 1242 1038
12 18 190 / 42 190 / 28 190 / 14 190 / 7 190 190 / 42 190 / 42 190 / 42 1350 1162
12 19 210 / 39 211 / 26 212 / 13 214 / 2 213 210 / 39 210 / 39 210 / 39 1458 1293
12 20 231 / 30 235 / 20 239 / 10 247 243 231 / 30 231 / 30 231 / 30 1566 1431
12 21 253 / 15 262 / 10 271 / 5 288 280 257 / 19 257 / 19 253 / 15 1674 1576
12 22 282 296 310 335 324 292 / 10 292 / 10 282 1782 1728
12 23 333 347 361 388 375 337 / 4 337 / 4 333 1890 1887
12 24 391 405 419 447 433 392 / 1 392 / 1 391 1998 2053
12 25 456 470 484 512 498 456 456 456 2106 2226
                       
13 14 120 / 3 120 / 2 120 / 1 120 / 1 120 120 / 3 120 / 3 120 / 3 936 708
13 15 136 / 9 136 / 6 136 / 3 136 / 3 136 136 / 9 136 / 9 136 / 9 1053 811
13 16 153 / 18 153 / 12 153 / 6 153 / 6 153 153 / 18 153 / 18 153 / 18 1170 921
13 17 171 / 30 171 / 20 171 / 10 171 / 10 171 171 / 30 171 / 30 171 / 30 1287 1038
13 18 190 / 42 190 / 28 190 / 14 190 / 13 190 190 / 42 190 / 42 190 / 42 1404 1162
13 19 210 / 48 210 / 32 210 / 16 210 / 11 210 210 / 48 210 / 48 210 / 48 1521 1293
13 20 231 / 48 231 / 32 231 / 16 232 / 5 231 231 / 48 231 / 48 231 / 48 1638 1431
13 21 253 / 42 255 / 28 257 / 14 262 / 1 259 253 / 42 253 / 42 253 / 42 1755 1576
13 22 276 / 30 282 / 20 288 / 10 301 294 277 / 31 277 / 31 276 / 30 1872 1728
13 23 300 / 12 312 / 8 324 / 4 347 336 307 / 19 307 / 19 300 / 12 1989 1887
13 24 337 353 369 399 385 347 / 10 347 / 10 337 2106 2053
13 25 393 409 425 457 441 397 / 4 397 / 4 393 2223 2226
13 26 456 472 488 521 504 457 / 1 457 / 1 456 2340 2406
13 27 526 542 558 591 574 526 526 526 2457 2593
                       
14 15 136 / 3 136 / 2 136 / 1 136 / 1 136 136 / 3 136 / 3 136 / 3 1071 811
14 16 153 / 9 153 / 6 153 / 3 153 / 3 153 153 / 9 153 / 9 153 / 9 1197 921
14 17 171 / 18 171 / 12 171 / 6 171 / 6 171 171 / 18 171 / 18 171 / 18 1323 1038
14 18 190 / 30 190 / 20 190 / 10 190 / 10 190 190 / 30 190 / 30 190 / 30 1449 1162
14 19 210 / 45 210 / 30 210 / 15 210 / 15 210 210 / 45 210 / 45 210 / 45 1575 1293
14 20 231 / 54 231 / 36 231 / 18 231 / 15 231 231 / 54 231 / 54 231 / 54 1701 1431
14 21 253 / 57 253 / 38 253 / 19 253 / 10 253 253 / 57 253 / 57 253 / 57 1827 1576
14 22 276 / 54 277 / 36 278 / 18 280 / 4 279 276 / 54 276 / 54 276 / 54 1953 1728
14 23 300 / 45 304 / 30 308 / 15 316 / 1 312 300 / 45 300 / 45 300 / 45 2079 1887
14 24 325 / 30 334 / 20 343 / 10 360 352 326 / 31 326 / 31 325 / 30 2205 2053
14 25 351 / 9 367 / 6 383 / 3 411 399 361 / 19 361 / 19 351 / 9 2331 2226
14 26 396 415 434 468 453 406 / 10 406 / 10 396 2457 2406
14 27 457 476 495 531 514 461 / 4 461 / 4 457 2583 2593
14 28 525 544 563 600 582 526 / 1 526 / 1 525 2709 2787
14 29 600 619 638 675 657 600 600 600 2835 2988

[15-Apr-1999]