The image to the right shows Albrecht Dürer's
famous engraving
Melancholia I.
Various interpretations of the image exist and
range from a depiction of a seeker
of wisdom in a mood of temporary defeat to an explicit warning against
obsessive study and its attendant destructive
melancholy. Whatever the correct interpretation, the variety of
magnificent symbolic and allegorical images contained in the engraving
hold an enduring fascination for us. Of particular interest for our
present purposes is the
magic square in the upper right of the picture
and shown in enlargement here:
The above magic square has rows, columns, and diagonals that all sum to 34. So do the corners, 2 by 2 subsquares at the corners and the center of the square, and clockwise elements on the outside in the same position relative to the corners, namely, 3 + 8 + 14 + 9 and 2 + 12 + 15 + 5. There are several other regular patterns in the square that also sum to 34. For many in Dürer's time, such a remarkable arrangement of numbers held deep mystical significance. For many people today, magic squares provide a motivation for explorations in various fields of mathematics.
Matrices
For our purposes, Dürer's magic square is an excellent example of a matrix, that is, a rectangular array of numbers. Each element in the matrix can be identified by two numbers, its row and its column. For example, in Dürer's magic square matrix, the 5 is in row 2 column 1 while the 14 is in row 4 column 3. If we denote a matrix as A, we may then store the elements of A by row and column. An element of the matrix may be written as A(row,column); thus, for example, for Dürer's magic square matrix A(2,1) = 5 and A(4,3) = 14. Again for this particular matrix, the diagonal sum A(1,1) + A(2,2) + A(3,3) + A(4,4) = 16 + 10 + 7 + 1 = 34, a property we already noted.
Matrices frequently arise in computational mathematics. The mathematical rules for manipulating matrices are well defined and easily implemented on computers. One of their primary uses is in the solution of systems of linear equations, which often arise in mathematical models of real world phenomena.
Sparse Matrices
Sometimes a matrix has a lot of zeros as elements. For example, consider the matrix below:
Of the 100 elements, only 17 are nonzero. The rest of the elements are zero. We call this a sparse matrix. While it is not costly to store all 100 numbers of the above matrix on a computer, consider what happens as the matrix gets bigger. If the number of rows grows to thousands or millions, the number of elements becomes too large to store. If, however, the number of the elements that are nonzero is small, we can still store the matrix if we only store those numbers and assume the rest are zero! This is a sparse storage scheme.
An example of sparse matrix storage is the coordinate matrix scheme. Here we define three arrays, which are ordered lists of numbers. The first array, call it rows, stores the row number of each nonzero element. The second, call it columns, stores the column number of each nonzero element. The third, call it values, stores the value of each nonzero element. The entries of each array must correspond to the same matrix element, and a reasonable arrangement would be to store the elements in order going across each row. Thus, for the sparse matrix above, the arrays could be rows = [1,1,2,2,4,4,5,5,6,6,7,7,8,8,9,10,10] columns = [2,7,1,6,3,10,4,8,1,7,5,9,2,4,10,3,8], and values = [3,1,1,7,2,7,5,8,2,6,9,4,1,7,4,7,5]. In this way we store only the nonzero elements and their locations in the matrix. In our example, the first entries are 1, 2, and 3, which indicate A(1,2) = 3 in our old storage scheme. The second entries are 1, 7, and 1, corresponding to A(1,7) = 1. The length of the rows, columns, and values arrays are each equal to the number of nonzero elements. For our example, we must store 17 x 3 = 51 numbers, which is less than the 100 we would have to store if we stored all the entries.
Even more efficient sparse storage schemes exist. For example, the Compressed Sparse Row (CSR) scheme has arrays giving the column number and value of each element and an array telling which element number is the first of the given row. Our sparse matrix example makes this explicit. For the above matrix, the columns array would again be columns = [2,7,1,6,3,10,4,8,1,7,5,9,2,4,10,3,8] and the values array would be values = [3,1,1,7,2,7,5,8,2,6,9,4,1,7,4,7,5]; however, we now have a row pointers array row_pointers = [1,3,4,4,6,8,10,12,14,15,18]. The first entry of row_pointers simply indicates the first element is labelled 1. The second entry of row_pointers tells us the first entry of row 2 is the third nonzero element of the matrix. The third nonzero element has column number 1 and value 1, as seen from the columns and values arrays; thus, in the old storage scheme, A(2,1) = 1. For the CSR scheme, the columns and values arrays still have length equal to the number of nonzero entries, but the row_pointers array only has length equal to the number of rows + 1. Notice that the actual value of the last row_pointer array is one more than the number of nonzero matrix elements. For our example matrix, we now must store 2 x 17 + 11 = 45 numbers, so the CSR scheme has saved memory over both the square array and the coordinate matrix scheme. These savings grow as the matrix becomes larger and/or more sparse.
Sparse Matrix Tool
Efficient routines exist for manipulating matrices stored in spare matrix format. The difficulty is in storing the matrix in the first place. One often wants to input a series of (row,column,value) triplets and then convert those data into one of the sparse matrix storage schemes. This conversion can be tedious without a readily available computer routine. An additional difficulty is that the sparse storage schemes require the data to be ordered, but in constructing the data in the first place, the data may not be ordered. For example, the triplet (5,2,10) may precede the triplet (3,4,7) in the constructed matrix input. Moreover, one often wishes to add the values of triplets with the same row and column number together. For example, if the triplet (2,5,3) and (2,5,7) both exist in the input, the final matrix should have an element with row number = 2, column number = 5, and value = 10.
The purpose of the Sparse Matrix Tool is to allow an internet user to upload an unordered list of (row,column,value) triplets in XML format. Once these data are validated, the server at Clemson University calls an efficient C program to store the data in a general sparse matrix structure and then output the results to three different sparse matrix storage schemes (the coordinate scheme, the compressed sparse row scheme, and the Yale sparse storage scheme). The user may graph the matrix and download it in ascii or XML format. The tool is intended as an easy-to-use means of generating and viewing sparse matrix output.
The best way to start using the tool is to try out the tutorials. More background and other related information is available from the Papers & Links sidebar link. We hope you enjoy the tool, and, as always, we welcome feedback.
