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

MDS User's Guide

Version 111, May 2009

To understand what the applet does you need to understand the Bernstein-Bézier form of a polynomial and the concepts of spline spaces and their minimal determining sets .

The Drawing and Analysis Modes

The main use of the applet is to analyze minimal determining sets. In the first few incarnations of this code that constituted the only possible use of the software. However, during the Spring Semester of 1999 my numerical graduate class persuaded me to add a variation of the Analysis mode that can be run as a two player game that's quite difficult and sophisticated and that I hope you will enjoy. It's described below at the end of this User's Guide. There is also a drawing mode described below which can be used to label domain points in various ways (without any analysis done by the code).

The Analysis Mode

As an illustration, the Figure nearby shows the Clough-Tocher Split, a set of three triangles that share an interior vertex. The partial minimal determining set shown is for the case that r=1 and d=6. Crosses in circles indicate points in the minimal determining set, filled colored circles indicate points that have been determined, and white circles indicate points whose status has not yet been determined. Boxes indicate points that do not enter any smoothness conditions. Other symbols may be substituted in the drawing mode.

To activate the applet.

Click in the box on the top of this page (or download the byte code and run it standalone, see below).

Two windows will pop up, the control panel, and a drawing window. The initial triangulation consist of three triangles sharing an interior vertex (the Clough-Tocher split). If for some reason you can't get the applet to work click here for a static image of the control panel and here for an image of the initial drawing window. (The eighth row of the control panel will not show up if you are using the applet rather than a standalone version of the code. This is because Java will not let the applet write on your machine, and I won't let it write on my machine. See below for information on how to save your work.)

If you click on the above applet to make the control panel and drawing windows disappear you can recover them in the state you dismissed them by clicking on the applet again, but only in the same browser section!

You can also download the byte file and run the program standalone. On a Unix system you'd invoke the program with the command java MDS. On my system the program is more responsive in that mode, I can run it with a specified amount of memory, it handles memory problems more gracefully, and I can save my work. .

Quitting.

To quit click on the upper left button (labeled Quit) of the control panel, or type 'x' in any drawing window.

The polynomial degree and the degree of smoothness.

You can change the values of r (the degree of smoothness) and d (the polynomial degree)in the third row of the control panel. There is one red textfield for r and one for d. To edit any text field move the cursor into the textfield and click (always the left mouse button) or highlight part of the text. Then type the insertion or replacement string. A change in any text window becomes effective only after you hit Enter (or Return) on you keyboard. The contents of the textfields can also be incremented or decremented (by 1) by clicking on the ">" and "<" buttons next to the textfield.

Constructing a Minimal Determining Set.

Suppose you want to construct a minimal determining set. You do this in stages adding one or more points at a time. Let's refer to the points you have already selected as the current set. The current set is always a subset of a minimal determining set, and eventually it becomes equal to one. To add a point to the current set just click on the domain point. The first time you do this some linear algebra will be initialized and any points that do not enter the smoothness conditions are added. The symbols you see have the following meaning:

Points in the current set can also be taken out, by clicking on them. Any points that are implied by the larger set, but not by the smaller, revert to their outlined status.

Adding and removing points in groups.

The menu in the fifth row of the control panel can be used to determine the effect of clicking on a point, according to the following options:

NOTE: Remember to switch back to point mode when done with one of the other modes. You can do this by using the menu on the control panel or simply by typing a period in the drawing window.

Adding Color

The current color can be changed using the second menu in the fifth row of the control panel. The default is black.

Having more than one drawing window.

You can have several drawing windows at once. The control window always corresponds to one particular drawing window. The drawing windows are numbered. You pick which one is currently associated with the control window by changing the number in the text field in the second row of the control panel, the one preceded by the string "T =". You can increase or decrease that number by clicking "> " or "< " on the buttons next to it. You can also edit the contents of the text window. The most convenient way of associating the control panel with a given triangulation is to type "c " or "C" in the relevant drawing window.

Editing a Triangulation

A rudimentary editing facility is available. Clicking on the button labeled Edit in the fourth row of the Control Window brings up an Editing Window. At the same time the current triangulation changes into a simple line drawing with the vertices being labeled.

The coordinates of individual points can be changed using the textfields in the second row of the Editing Window.

In the third row the indices of three points can be chosen. Clicking on the button Align will change the coordinates of the third point P to move it close to being in one line with the first two points P1 and P2. The program first moves P to the pixel closest to the projection of P onto the line L through the first two points. It then searches the neighborhood of that pixel for a pixel that is actually on L. It avoids making points coincide. The search may be unsuccessful, for example if P is in between P1 and P2 and the differences of the x and y coordinates of P1 and P2 are two distinct prime numbers. You may be able to make the alignment possible by changing slightly the coordinates of P1 or P2 first. Pairs of parallel edges sharing a vertex are drawn in red.

The Buttons in the top row do the following:

Enumerating Triangulations.

This mode lets you enumerate triangulations with certain attributes and study their properties. It can be invoked from the menu in the fourth row. Much more information can be found here.

Triangular Finite Elements

This mode allows the design of triangular finite elements. Much more information can be found here.

Miscellaneous Options

The following is a list of options available on the control panel. not yet discussed:

Progress Indicators

During certain time consuming process the drawing window indicates what's happening. The word Initializing is present during the initialization of the linear algebra , and a moving colored bar indicates progress. In particular the bars indicate:

Keyboard Commands

Several Keyboard commands are available in each drawing window. The list below will be extended in the near future. The idea is that essentially one should be able to control each drawing window without using the control panel at all.

D increment d by 1
d decrement d by 1
R increment r by 1
r decrement r by 1
0 make current color black (the default)
1 make current color red
2 make current color green
3 make current color blue
4 make current color cyan
5 make current color magenta
6 make current color yellow
7 make current color White Note: use this color with caution and only for special effects because the background of the drawing is white and the interior of circle and square outlines is also white.
RETURN redraw the net
o,O restart
p Turn position indication during Custom Design OFF
P Turn position indication during Custom Design ON
q,Q hide window
x,X exit system
c,C associate the control panel with this window and put it on top
. point mode
/ edge mode
@ ring mode
# disk mode
$ triangle mode
all mode all mode
F1-F12 choose a triangulation (see above)
l label the vertices, toggle between omitting and including boundary vertices
S Enter Super spline mode.
I Initialize MDS computation.
m or M List the current set to standard output.
u or U Undo the previous step in designing a custom triangulation. This can be repeated. Can also be used to undo the last step taken in the drawing mode, but in that case the command can be used only once.
z Toggle the listing in the drawing window of the indices of the domain point that the cursor is currently pointing to. This feature is useful when working with b-nets of very many domains that are close together. The default is off. This is an experimental feature. The display sometimes gets confused, and can be restored by redrawing the net, e.g., by hitting the return key.
< and > Decrease or increase the current symbol Size.
If the keyboard command is not recognized a message is sent to standard output.

Text Output

At present, textual information (to standard output) is very sparse. When a triangulation is completed it is described. The dimensions and rank of the original matrix is stated and a list of the prime numbers used is given.

For example, the default Clough-Tocher split with r=1 and d=3 causes this description: 


MDS:  Version 3.0, November 1998   run # 1308
 New Triangulation
4 Vertices
0:   (300,383)
1:   (524,525)
2:   (300,100)
3:   (76,525)
3 Triangles:
0: 3 1 0
1: 3 0 2
2: 0 1 2
3 boundary edges:
0: 1 3
1: 2 3
2: 1 2
3 interior edges:
0: 0 1 --- 3 2
1: 0 3 --- 1 2
2: 0 2 --- 3 1
3 boundary vertices:  1 2 3
1 interior vertices:  0
 interior vertex 0 E = 3 e = 3
r = 1 d = 3 lower bound = 12
19 Bezier Points
 using 1 primes: 
0 2147483647
 The original matrix is 9 by 19 and has rank 7
 The dimension of the spline space = 12

Most of this information is readily understood taking into account the fact that the interior vertex of the Clough-Tocher split is vertex 0. The vertices coincide with specific pixels whose coordinates are integers, with the origin in the upper left corner, x increasing to the right, and y increasing downwards. An interior edge is described by the pair of indices of its vertices, and the indices of the remaining vertices of the attached triangles. For example, "0 1 --- 3 2" means the interior edge is the edge shared by the triangles (0, 1, 3) and (0,1,2).

For each interior vertex v, E is the number of edges attached to v, and e is the number of different slopes these edges have. For example, the four edges emanating from a singular vertex form two parallel pairs, so E=4 and e=2.

The lower bound given is known to equal the exact dimension of the spline space whenever d>3r+1.

Typing "s" (for statistics) in the drawing window causes information like this (obtained after clicking on " complete" in the default setup) to be displayed: 


 checking ... 
7 equations 12 active variables
 equations OK ... 
 fill = 29/84 (34%)
 total of 597 Residuals
 The likelihood of no accidentally zero residuals is 99.999%

This means the reduced system has 7 equations in 23 active variables. 29 entries in that matrix are non-zero. The phrase "equations OK" is a leftover from the debugging days - it means the coefficients in each equation add to zero. They must since the function that equals 1 everywhere is a spline all of whose Bézier coefficients are 1. Please let me know it you ever get a message that the equations are not OK! The "total number of residuals" is the number of times a residual was computed since the last initialization of the linear algebra.

The word "fill" indicates the number of non-zero entries in the matrix compared to the total number of entries.

In the above example a total number of 597 residual has been computed so far. (That number can easily climb into the millions.)

When only one prime number is used the likelihood that none of the computed residuals of non-zero matrix entries is zero is displayed. This is based on the assumption that all residuals are equally likely. The likelihood is usually close to 100% if the default prime of 2 31 -1 is used. You may find it interesting to examine this likelihood for small prime numbers. When several prime numbers are used the likelihood of an accidentally zero residual actually increases, but the likelihood of a correct minimal determining set increases, so the likelihood statement is omitted. For more information check the page on residual arithmetic.

The Srd Calculator

Dimensions and lower bounds on the dimension can be computed by using the Srd Calculator. The calculator does not require analysis of a linear system, saving a potentially large amount of time, and you may find it interesting to compare the lower bound with the actual dimension of your spline space.

It is a separate window that can be invoked by clicking on the button in the upper right corner of the control panel. Essentially it computes a lower bound on the dimension of the current triangulation of the form

dim S <= A V B + B V I C + sigma (*)

which is explained here. The bound equals the true dimension whenever

d > 3r+1

and in many other situations also. It becomes less reliable as the polynomial degree decreases.

When the calculator is brought up it shows the lower bound (*) for the current triangulation and the current values of r and d. The lower bound is displayed in the lower right corner of the calculator window. Usually That expression gets updated automatically whenever the triangulation (or r or d ) changes. However, the values of r, d, V B , and V I can be changed on the calculator panel itself, and the values of A, B and C will change accordingly.

This facility is most useful for examining the dependence of A, B, and C on r and d. It is less useful to change V B and V I since the resulting value of the lower bound does not apply to any particular triangulation.

A little more subtle is the value of e V that can be changed in the right most text field in row 2. If it is white with no text in it it has no effect on the number in the third row of the panel. However, if you enter a number then the number sigma in the third row will equal

You may find it interesting to study the dependence of sigma on r, d, and e V , but the lower bound in the fourth row will have a very arcane meaning.

The Hide button hides the calculator window. (You can recover it by pressing on the Calc. button in the control window.) The Get button synchronizes the calculator with the current triangulation (the one associated with the control panel).

Every update of the calculator also causes an appropriate line of text to be written.

Designing a Custom Triangulation

The image nearby shows the domain points for C 1 cubic on a custom designed triangulation. The dimension of this space in general is believed to be 3V B + 2V I + 1 plus the number of singular vertices. The example shows 3 domain points associated with each boundary vertex, 2 with each interior vertex, and one additional point (the lone blue plus sign in the center of one of the interior triangles).

You can design your own triangulation by selecting the three vertices of the first triangle and then adding flaps (new triangles joined to the old triangulation along one edge) and fills (new triangles joined along two edges). Follow these steps:

  1. Select custom mode by using the menu on the control panel or by typing F1.
  2. Draw the first triangle by moving the mouse to the intended locations of the vertices and clicking there. To facilitate precision, once you have placed the first vertex the coordinates of the mouse position relative to the first vertex will appear in the drawing window. You can turn this option off by typing p (for position) and turn it back on by typing P.
  3. Add flaps by moving the mouse to the midpoint of the newly to be interior edge and dragging the mouse to the intended location of the new boundary vertex. Once you let go of the mouse button that vertex cannot be moved. The location of the new vertex is indicated as described above.
  4. Add a fill by clicking on the newly to be interior vertex.
  5. If you do not like the triangle you just added type "u " to undo your choice. If necessary this process can be repeated until all triangles are gone. You can also abort adding a flap by moving the mouse outside the drawing window.
  6. When you are finished with your triangulation type "f " or "F" in the drawing window. You can now use this triangulation like any of the others.
  7. To return to the design mode click on the button labeled "Again" in the control panel.

Importing a Triangulation

Pressing the button labeled "import" opens a new window that lets you load a triangulation from a file (only in stand-alone mode) or a URL. The file needs to contain the following data: V and N on the first line, followed by V lines containing the coordinates of the points, one point per line, followed by N lines containing the indices of the vertices of each triangle, one triangle per line. The integers must be separated by blanks, and the lines must not contain other data. For example, the file for the CT split would be: 
4 3
302 88
80 514
521 514
301 372
2 0 3
2 3 1
3 0 1
The Save Button saves such files with the extension .cmb

The Drawing Mode

The drawing mode is invoked with the menu in the third row. You can first do some analysis in the analysis mode and then switch to the drawing mode to change some of the symbols. However, if you switch from drawing mode to analysis mode then the drawing window gets reinitialized, so beware!

Several symbols can be used. They are selected by the menu in the fourth row and illustrated in the Figure nearby. Everything on the control panel works as in the Analysis mode when it makes sense. (For example, it does not make sense to ask the applet to color all the points in the minimal determining set.)

In the single point mode (selected by the first menu in the fifth row) clicking on a point that has already been labeled with the currently selected symbol causes that symbol to be replaced with a circle. (This is like removing a point.) In the ring, disk, and triangle modes points are marked with the selected symbol regardless of their prior status. In the " all" mode all points as yet unmarked (indicated by single thickness circles) are marked with the currently selected symbol. In the "replace" mode all points marked as the selected point are marked with the selected symbol. Changes made in any but the point mode can be undone by typing "u ".

Manual Control of Symbol Size

Normally the size of the symbols drawn in the drawing window is determined automatically and depends on the current density of domain points. However, it can be set manually for special purposes. Click on the button labeled Symbols (in the second row of the main control window). A new window, the size control window, appears. The symbol size (in pixels) is displayed in its text field. It can be changed with the two arrow buttons or by entering a new size in the text field. Clicking on "Default" in the size control window replaces the symbol size with its usual automatically computed value. Clicking on automatic in the size control window, or again on Symbols in the main control window, causes the size control window to disappear and symbol size control to revert to automatic. While manual control is in effect the symbol size will not change if the density of the domain point changes, for example in response to changing the value of d or picking a new configuration. The current triangulation is redrawn whenever the current value of its symbol size is changed manually.

Saving Your Work

It is possible to save your work, but for security reasons Java will not let my applet write on your machine (and I won't let you write on my machine). You need to download the byte code as described in the next section. If you run that code (directly rather than via a browser) on your system there will be an eighth row on the control panel (shown on on this static image) which lets you specify a file name and read and write to that filename.

The individual items in the 8-th row do the following:

Notes: Any restoration takes place in a new drawing window. Thus you can explore different branches using the Object button, or retract your steps without loosing your work using the Restore button.

Saving High Resolution Postscript Images

Pressing the button ps on the control panel brings up a new panel that lets you save the contents of the drawing window as a high resolution postscript image. The text field on the postscript panel lets you specify a file name, the save button actually saves the file, and the ColorMode button toggles between full color mode and gray scale (which may be required by some publishers). The menu on the postscript panel lets you specify several image sizes and aspect ratios, as follows:

Interfacing with Other Codes

The buttons labeled "CODE", "DOUBLE ", and "QUADRUPLE", in the bottom row of the control panel computes data in floating point form and save them to a file s.code where s is the string determined by the other items in this row. Saving the "CODE", information can also be invoked by typing w or W in the drawing window. The bars in the drawing window in turn show progress in setting up the floating point equations, reducing the system to triangular form, and then reducing it to diagonal form. The primary contents of the s.code is the matrix C where

d = Cc,
c is the vector of coefficients whose domain points are in the minimal determining set and d is the vector of coefficients that's determined by the smoothness conditions.

The files s.code differ in subtle ways. Click on the links below to see the file for the cubic C 1 CT scheme.

The buttons "DOUBLE" and "QUADRUPLE" also produce a file s.explicit which contains an exact rational representation of the determined coefficients in terms of those corresponding to the minimal determining set.

Super Splines

Super splines are splines that satisfy additional smoothness conditions. (They thus form a subspace of an ordinary spline space.)

To examine a super spline space do the following:

  1. Bring up the triangulation you want and set r and d as usual.
  2. Enter Super spline mode by clicking on the red button marked "Super", on the left in the third row of the control panel. Or achieve the same effect by typing S (in the drawing window).
  3. To increase smoothness around a vertex click on the vertex. Each time you click the smoothness requirements are increased by one. They are indicated by yellow quadrilaterals.
  4. To increase smoothness requirements across an edge click close to the center of the edge. These additional conditions are indicated by Cyan quadrilaterals.
  5. You can also increase smoothness requirements by typing + or decrease them by typing -. These typed commands apply to the last object (vertex or edge) selected by clicking.
  6. You can also impose additional individual smoothness conditions which are indicated by magenta quadrilaterals. To do so proceed as follows:
  7. To initiate the MDS analysis click on Init! in the second row of the control panel, again click on SUPER, or type I I.
  8. To modify the supersmoothness conditions return to superspline mode by clicking on the "Again" button next to the "Super" button.

Notes:

  • Once you enter Super spline mode you cannot exit it without resetting.
  • You remain in super spline mode (and maintain the current additional smoothness conditions) if you change d or r. However, there is no intelligent adjustment in the degrees of the additional smoothness conditions.

    • Reduced Polynomial Degree

    It is possible to impose additional conditions that force the splines to have a reduced polynomial degree on selected triangles. This option is treated like a superspline condition although it is conceptually different. To reduce the polynomial degree on a certain triangle by 1 enter superspline mode and click close to the center for the triangle. The triangle will be drawn in green, and the (reduced) polynomial degree will be drawn in red, close to the center of the triangle. That red number may be partially obscured by the B-net which is also drawn. The + and - keys work as they do for the superspline conditions, + increase the polynomial degree (up to d ) and - decreases it. Here are are some examples of polynomials with lesser degrees than meets the eye.

    Computing Bounds

    Pressing the button labeled Bounds in the sixth row of the control panel turns the computation of bounds on and off. The best available current bounds are displayed at the top of the drawing window. The feature is on by default. This is an active research topic under current investigation.

    Running Standalone and Downloading the Code

    This code is under development. To take advantage of new features and bug fixes you may want to keep returning to this page rather than download the code. However, you may download the byte code of this software and incorporate it into your own web pages or run it on your system in a standalone mode. You need the following Java classes:

    Alternatively, on a Unix system you can download the single file message , put it into an empty directory, and type source message . This will unbundle the class files and bring up the MDS code.

    Details of how to run the byte code on your machine depend on your operating system. On my (Unix) machine the command 

    java MDS
    invokes the program. You need to be connected to the directory containing the byte code. Type 
    man java
    to obtain information on options you may be able to specify. For example, on my system the command 
    java -ms128m -mx128m MDS
    will cause the program to run with 128 Mbytes of memory allocated to it (in place of the default 16Mbytes).

    Printing Triangulations

    You can save the image of a triangulation to a postscript file or directly print that image. To do so click on the Print button in the first row of the control panel or type Control-P in the drawing window. This facility works only in the standalone mode. If run from an applet, a security exception occurs.

    Assigning Polynomials

    For test purposes (e.g., checking polynomial precisions) polynomial coefficients can be assigned on one triangle. The software can the compute the coefficients of the same polynomial on all other triangles. To use this feature click on Polynomial in the control panel, fill in the coefficients in the new Polynomial panel, and click on Assign in the Polynomial Panel. The resulting coefficients will show in the drawing window.

    Known Bugs

    The following bugs are known at present and will hopefully be removed in the future:

    Performance

    The following table gives an indication of the capabilities of the code. The underlying triangulation is the generic double Clough-Tocher split with d=2r for r=1,2,...,10. The columns in the table have the following meaning:

    generic double-Clough-Tocher split, d = 2r
    r d m n rank dim fill save
    1 2 24 22 16 6 82% 8
    2 4 84 79 61 18 80% 28
    3 6 180 172 138 34 79% 87
    4 8 312 301 244 67 82% 240
    5 10 480 466 381 85 82% 504
    6 12 684 667 547 120 86% 984
    7 14 924 904 745 159 83% 1,728
    8 16 1,200 1,177 972 205 86% 2,864
    9 18 1,512 1,486 1,231 255 80% 4,464
    10 20 1,860 1,831 1,518 313 76% 6,856

    The MDS Game

    The mode menu (the second item in the third row of the control panel) lets you select a game mode in which you can construct a MDS taking turns against an opponent who's trying to determine more points than you.

    To explain the rules we need to distinguish between points you or your opponent add to the current set, and points that count towards your victory. Let's call the latter cookies to avoid confusion.

    The rules are as follows:

    1. You get a cookie for every domain point whose Bé zier ordinate is determined by a point you add to the current set.
      2. The player ending up with the largest number of Cookies wins.
    2. You and your opponent take turns
    3. You turn is over if you get at least one cookie, or after you add the second point of your move to the current set. The program indicates whose move it is.

    Notes

    Have fun!

    Write to me

    Please write to me if you encounter any bugs or you like to make suggestions for additional features.

    [05-May-2008]