Working with Matrices

The provided CMatrix class manages 2-dimensional matrices. The members of a CMatrix may be numbers, as in the classical mathematical sense of a matrix, or they may be any other type of Lua object, such as strings or userdata (objects). This topic describes how to work with matrices using the CMatrix class.

Matrix Indexing

The CMatrix consists of rows of CMatrixRow objects, with each CMatrixRow managing the values at column indices. Depending upon the situation, you can access the members of the matrix by subscripts in [a][b] form, or using one of the Get... methods in the CMatrix class. For example, suppose a CMatrix exists and has an element at rowj, column i. Then the value of the element at rowj, column i can be retrieved using any of these 3 methods:

1.   value = M[j][i].

2.   value = M:Get(j,i)

3.   row = M:GetRow(j) ; value = row:Get(i)

In method 3, above, notice the use of a semicolon (;) to separate two statements. The first statement obtains the (which is a CMatrixRow object) at index j. The second statement then getsvalue from column i of that row. This code assumes that rowj exists and has an element at index i. If using method 3, you might wish to test that row is not nil before fetching the value, using an if block like this:

row = M:GetRow(j)

if (row) then

  value = row:Get(i)

else

  value=0

end

In this version, the code returns value=0 if the row is empty (nil). You might choose some other special value other than 0 to signify an empty row.

Types of Matrices

Packed Matrix

A filled matrix has a value in every element. An image is a case of a packed matrix; every image pixel has a value.

Suppose we have a matrix like this, consisting of 4 rows of 6 elements each. We say this has 4 rows and 6 columns, making 24 elements in total:

Every element is used so, when performing most calculations, we loop over the matrix by accessing each column in every row. The matrix above requires memory space for 4 x 6 = 24 values. Suppose we had a 1000 x 1000 matrix like this: that would require memory space for 1 million values. Looping over the elements during a calculation on the full matrix would take 1 million loops.

Sparse Matrix

Consider the following 4 x 6 matrix that has some elements undefined:

This matrix uses some of the same values as above but more than 1/2 the elements are missing. To store this in memory in the traditional packed matrix format, we still need space for 24 elements but 16 of them will have dummy values such as 0. Perhaps the 0 values do not affect the calculation. But to access the elements in a traditional protocol still means looping over 24 elements in 4 rows of 6 elements each. Notice that the value "1204" at column 6, row 1 causes the matrix to require 4x6=24 elements rather than 4x4=16 elements, which itself has a large effect on memory space and the performance of calculations. Now imagine the worst case scenario of a 1000 x 1000 matrix consisting of the above sub-matrix plus one element at coordinate (1000,1000). Not only does the image require space for 1 million values with 9 of them valid, but perhaps worse still is the fact that a calculation that uses these 9 elements still requires 1 million loops and the loading or testing of 999,991 possibly useless zero's. These are cases in which a matrix is full of zeros which are meaningful, but that is not the case we are considering. Here we are considering the case of a sparse matrix in which many, if not most of the available cells do not contain a meaningful value.

As an alternative viewpoint, consider a matrix to be a collection of independent rows. Then let each row contain however many values it needs, and let the matrix use only as many rows at it needs. Consider the 4x6 matrix, above, with an element at index (1000,1000). Clever data structuring would allow us to store such a sparse matrix in memory using only 5 rows, with the longest row containing only 3 elements! In total, we would need to store the address of 5 rows and then the values for 3, 2, 2, 1, and 1 elements respectively. In addition to the memory advantage, the gain in calculation performance would be tremendous. Fortunately, creating a vector or a matrix in Lua uses its table paradigm which stores pair values. Each pair consists of an index and a value. Therefore we make a matrix in Lua as a collection of tables, one table storing pairs for the row index and row address, and the other tables storing pairs of column index and value for each row. For a sparse matrix having m columns andn rows, then there are then n+1 tables. One of the tables contains (row index, row address) pairs to access only the rows that are defined. All the other tables contain the (column index, value) pairs which may be different for each row. The CMatrix class uses this method. All matrices are treated as sparse, regardless of whether they are completely packed or extremely sparse. In fact, each matrix row is a CMatrixRow class which is a wrapper around a Lua table of (index,value) pairs. If the matrix is sparse, this provides the storage and performance gains described above. However if the matrix is packed and large, you might consider creating the matrix as a CImage and using the class methods to operate on it at the speed of optimized C++ code.

Matrix Formats

The code examples below illustrate ways of accessing a CMatrix. If every element of the matrix is important, then we need to use the full access method. This example shows how to loop over the rows and columns of a CMatrix M. In this example, we will consider a matrix to be an x,y grid of height values and use the Volume method to compute the total volume of the solid object.

Accessing Every Element

The example below shows two ways to access every matrix element in the traditional "rectangular grid" approach. If a matrix element is not initialized (its value has not been set), the CMatrix:Get method returns its value as 0, which does not affect the calculated sum but does require CPU time. Here, we use the simplest, most brute-force methods to loop over every matrix element. We use a naive indexing method involving M:Cols() and M:Rows() to get the dimensions of the matrix. These require recalculating the number of rows and columns each time the loop index is tested. In addition, the address of the value is calculated usingM:Get(j,i) or every matrix element:

Example 1. One way to read every matrix element

In a large loop involving tens of thousands of indices or more, we could improve the above function simply by moving the loop limits M:Cols() and M:Rows() out of the loop. This is a minor improvement but worth the effort for large loops:

Example 2. Improved way to read every matrix element

Another problem is that the for loop tests every index between1 and n:Rows() and between1 and M:Cols(), even if no value is defined at a given index. If no value exists, then M:Get(j,i) returns 0. This does not change the outcome of the calculation but does use processing time to lookup the index and add 0 to the sum. We could also test every index and not add it to the sum. But if the matrix has many undefined values, Lua's built-in support of sparse matrices can provide a vast improvement in loop processing. This is described in the following section.

Sparse Access

This example shows how to use the "in next" and"in pairs" Lua syntax to loop over the sparse matrix, avoiding uninitialized rows and columns. Use this protocol if many of the indices i andj do not exist (i.e., are not initialized) in the matrix. In this protocol, not initialized elements are not used and require no CPU time to ignore.

Using sparse protocol to read every matrix element

The nice thing about sparse access is that it works for both cases: when the matrix is full and when the matrix is sparse.

Changing Values in a Sparse Matrix

The above code works for fetching values from a sparse matrix. However, it does not work for setting values in a matrix. There are two reasons why it does not work:

4.   The loops index over existing entries in the matrix. and

5.   A value fetched from the matrix becomes a local value so that changing it does not change the value inside the matrix.

Let us look at how to change the values of existing entries in the matrix. Here we use each row reference to access the values inside it. Since each row is a CMatrixRow of column data, the CMatrixRow:Set method is used to change the value of row members:

Example 1. Setting values in a sparse matrix

We should make one change to the code above. Since a CMatrix can contain any type of data—such as strings or objects, in addition to traditional numbers—we should check that each matrix member is a number before doing math on it. The following small change accomplishes this:

Example 2. Setting values in a sparse matrix

Initializing a Matrix

The example below shows one way to fill a rectangular matrix with the same value. Lua interprets[] following a table name as subscripts for indexing the table. This notation makes it handy to setup a matrix. The script below shows a simple—if not optimal—way to setup a matrix having 4 rows of 6 columns each.

Initializing an n x m matrix

Notice that the Init function takes 3 arguments: the number of rows, the number of columns, and the initial value. The matrix M is declared as local inside the function so that itsname does not collide with other M names outside the function. But the function makes it visible to the world in a hidden way by returning a reference to it. The caller can assign the returned matrix to any name it chooses using a syntax like this:

     MyMatrix = Init( 1.0, 4, 6 )

Also in the above example, M is declared inside the function as a local value. This declaration keeps the global namespace from being polluted by the nameM. Thus M is private: inside the function, it references a table; outside the function, the name M may be used for any other purpose.

Using the CMatrix Class

The other alternative for working with matrices is to use the CMatrix class. That class provides rich functionality for working with 2-dimensional matrices using a class metaphor. The CMatrix class handles both sparse and packed matrices in an efficient way.

To realize the matrix initialization shown above, we would write the following lines of script:

Initializing an n x m CMatrix

Related Topics

CMatrix class

CMatrixRow