Fill-In User's Guide

Obtaining the Code

You can invoke the fill-in code directly from the above applet, or by downloading the binary java class files. Downloading the code is preferable for extensive work, you have better control over memory requirements, and you may be better able to access local files and process the text output from the software. You need the following files:

Once you have those three files start the code with a command such as

java fill

The Control Panel

After clicking on the applet at the very top of this page, or invoking the downloaded code, a control panel will appear. If this does not work, for your information you can see a static image of that panel by clicking here. (In that case you probably also cannot see the applet. You need to get a java enabled browser or computer.)

Operation of the panel is very simple: You select values of m and n and click on Go to see the filled in matrix. Following is a more detailed explanation of the individual items of the control panel.

Row 1:

Go starts the computation of the filled matrix. You can click on Go whenever it appears red. When it is gray an ordering is being computed. This may take longer than the computation of the resulting fill-in. Clicking on Go during that period has no effect. Once the computation of the fill-in begins a new window appears that shows the resulting matrix. You can then start a new computation, even while computation of the fill-in is still in progress.
Stop interrupts the most recently commenced computation of an ordering or of fill-in. It has no effect on computations that may have started earlier and are still ongoing. You can interrupt and dismiss previously created matrix windows by typing x or X in them.
Quit stops all computation and dismisses all windows. If you invoked the code through the applet, clicking on the applet has the same effect. (Clicking on the applet for the third time brings up a new control panel in its initial state.)

Row 2:

The two text fields contain the values of m and n, respectively. They can be entered by typing in the text field. You must hit the Enter key after typing the relevant number!

Increment buttons The green increment buttons increment or decrement by 1 the number in the text field that they surround.

The blue button labeled = sets m equal to n. Thus if m and n are equal you can enter the value in the right text field and then click on =.

The blue button labeled <-> interchanges the value of m and n.

The Method Menu let's you choose the method of ordering:

Import: read the ordering from a file or URL, see below.

Lexicographical: the points are labeled in the sequence in which we would read them.

Cuthill-McKee.

Nested Disection.

Red-Black Ordering.

The Greedy Algorithm.

Maximum Greed. This attempts to maximize the fill-in by always picking a node with the maximum number of neighbors. In that sense it's the converse of the greedy algorithm.

Greed A. This variation of the greedy algorithm picks among all those nodes of minimum degree one where the sum of the degrees of neighbors is as small as possible.

Greed B. Conversely, this variation picks among all those nodes of minimum degree one where the sum of the degrees of neighbors is as large as possible.

Minimum Fill. This ultimate greedy algorithm picks a node which minimizes the actual fill-in at that elimination stage.

Random. Included for comparison purposes, this option generates a random labeling. Those labelings will differ if the option is run repeatedly.

The last menu in Row 2 let's you reverse the ordering. It has no effect if it shows a blank entry.
Row 3: This row lets you import an ordering. Select file or URL from the menu and enter the file name or the URL in the two text fields. The strings in the two windows will be stripped of leading and trailing blanks and then concatenated. Usually the left window will contain a directory name or a web site, and the right window a file name. To try this feature enter the URL http://www.math.utah.edu/~pa/fill/lexi66.dat and you will see the file for a 36 by 36 matrix corresponding to lexicographical ordering. The file must contain the values of m and n in the first row, separated by a blank space. The remaining rows must contain the labels, one per row.
Row 4 contains the title that appears on the drawing of the filled matrix. It is automatically generated but you can replace or modify it by typing in the text field just prior to clicking on Go. (Remember to hit the Enter key!)

The Matrix Windows

Filled matrices are displayed in individual windows. You can see examples on the introduction page. You can have as many matrix windows open as you like, or as your computer can handle. You can dismiss the last generated matrix window by clicking on the stop button of the control panel. You can also dismiss any particular matrix window by typing x or X in it.

The matrix windows show matrix entries as green if they are originally non-zero, or red if they become non-zero in the elimination process. Otherwise they are dark blue or (very) dark green.

Matrix windows are automatically sized to fit a reasonable screen size. There are two types:

Dark Blue Matrices with a light blue background have at least one pixel per matrix element.
Dark Green Matrices with a gray background have several matrix entries for each pixel. Each pixel is red or green if at least one of the matrix elements corresponding to the pixel is non-zero.

Each matrix window has a text at its bottom, and also as its name, that gives details of the fill-in. An example illustrates the information. Suppose the text is

3:  m = 10 n = 10 lexicographical  100 x 100 64 p/e  f = 729 = 14.58%

This text indicates matrix window number 3, with the numbering starting at 0. m and n have the indicated values, in this case 10. The string "lexicographical" describes the ordering. The matrix is N by N where N=mn. In this case, N=100. There are 64 pixels per matrix entry. The string e/p in place of p/e would indicate the number of matrix entries per pixel, for large matrices. The fill-in is 729 for a triangular matrix factor. Twice that number is given as a percentage of the whole matrix size, i.e., N squared. This text is generated automatically. You can specify any other text you like in the control panel just prior to clicking on Go.

Standard Output

The code writes to standard output. If you run the code by clicking on the applet that output will appear in the Java Console which is usually invisible unless you bring it up manually. The details of the console operation depend on your browser.

The output may contain diagnostic and error messages. Normally, however, it consists of the following items:

A date and a version a number
For each matrix:
- An m by n table giving the labels in the matrix graph.
- A copy of the line, described above, with details of the fill-in.

Technical Notes

As the size and number of the linear systems increase the code requires more resources in terms of time and memory. You are likely to run out of patience before you run out of memory, particularly if you download the code and allocate memory to it manually. However, the product of m and n must not exceed 46,340. Beyond that number parts of the index arithmetic in the code would overflow the integer word size in java.
If you do run out of memory you may be able to recover memory, and continue your work, by deleting some of the open matrix windows. (Type x or X in those you want to get rid of.)
This software has been designed for interactive experimentation. It is not particularly fast. For the actual computation of optimal orderings of large matrices one would likely want to use a faster special purpose code.
Reversing the ordering may have no effect at all, for example, in the lexicographical ordering, or a huge effect, for example in the greedy algorithm.
Similarly, interchanging m and n may have a large or a small effect.
The greedy algorithm may require more time for the computation of the ordering than for the computation of the fill-in. Of course, if you actually solve several linear systems with the same structure the ordering would have to be computed only once.
The values of m and n specified in the control panel have no effect when importing an ordering. After the imported file is read they are reset to the values specified in the file.
The code uses a hash table to keep track of zero and non-zero entries in the coefficient matrix.