Computational Mechanics Australia Pty Ltd
The Company Products Contact
CMA-LS-SPARSE: Solution of Large-scale Least Squares Problems and Systems of Linear Equations with Sparse Indefinite Matrices.
Systems of linear equations with large sparse matrices are common in many fields of mathematical modeling and processing of information in general. Such matrices can have specific properties: they can be positive definite for some classes of problems (like Finite Element Modeling), or indefinite in general case. They can also have unequal number of rows and columns. In case if the number of rows exceeds the number of columns, and the rows are not linearly dependent, the corresponding system of equations is over-determined, so a solution can only be obtained in terms of least squares .

For the solution of large sparse systems with positive definite matrices, our company developed a very efficient product CMA-SPARSE, which can solve systems of several million of equations.

CMA-LS-SPARSE (LS standing for "least squares") is a further development of the CMA-SPARSE product. It allows processing of general-case sparse matrices, even those arising in over-determined cases.

There is a number of applications where CMA-LS-SPARSE would be the tool of choice. One such application is image processing.

This example is an illustration of how the program can be used with a general-case sparse matrix, which is not supposed to have any specific (spectral, etc.) properties. The example is real, and is taken from the image processing algorithms, when blurred images are restored to a more reasonable quality, based on the features of pixels surrounding a particular pixel where more realistic grey hue should be restored.

The image is supposed to be monochromous (grey), and it consists of N-by-M pixels, where N indicates the number of lines, whereas M is the number of columns. As a simple example, we chose to artificially blur and then de-blur a small part of a larger image; both images are shown below.
Original small greyscale image 64 by 64
The square 64-by-64 pixels image (shown above) has the total of 4096 pixles. It was artificially blurred, and then restored using an algorithm that, for each pixel takes the information from the same line, namely: four pixels to the left and four pixels to the right.

The global matrix of the system of linear equations will have the dimensions 4096-by-4096. It is block-diagonal, with each block having a particular structure of elements, where s=1./9., or 0.1111111111111.... Generally speaking, the global matrix is block-diagonal, each block being an M-by-M matrix, as shown below:

Single block of the matrix

The global matrix looks as follows, where the total number of diagonal blocks is N :
Matrix block diagonal
It must be emphasized that the program treats this example as a general-case sparse matrix, i.e. its actual structure doesn't matter: the program just receives the matrix non-zero elements and their indexes one-by-one.

Processing of large images leads to a necessity to solve systems of linear equations of sizes up to hundreds of thousands or even millions. As an example of a somewhat larger problem than the previous one, we take blurred version of the full flower image shown on the left in the example above. The blurred image is then sharpened using the same algorithm. The to-be-restored image has the size of 149 lines by 227 columns. In this particular instance we created a blurred version of an original image ourselves. Since the FFT (Fast Fourier Transform) algorithm works with images that must have numbers or rows and columns being powers of 2, we had to introduce additional (empty) rows and columns into the original image. Therefore, the blurred image has the size of 256-by-256, and the matrix size is 65536. After the restoration we remove the earlier added rows and columns in order to bring the restored image to its original size.

CMA-LS-SPARSE solved that system of linear equations in less than 3 seconds on a computer with Quad-Core Intel Celeron processor N3450 (for the purposes of testing, we deliberately selected a relatively low-performance processor, in order to demonstrate that the program is very efficient in any case).

Flower 149 by 227
Our third example is a relatively large image of Moon surface sized 989-by-1000. Smaller versions of blurred and restored images are shown below; we also provide references to the full-sized images.

Blurred image of original size.

Restored image of original size.
Flower 149 by 227
Flower 149 by 227

The corresponding linear system contains 1048576 equations. It has been successfully solved on the same Intel N3450 processor in 207 seconds. It should be noted that the CPU time used to solve each particular system may vary significantly, depending on the such parameters as average number of non-zeros per matrix row, the matrix condition ratio, etc.

CMA-LS-SPARSE is an absolutely unique tool, suitable for solving very large (up to several million equations) sparse linear systems with general-case matrices, including over-determined systems. What makes this product unique ?

  • You can compile and run it on any modern desktop or laptop computer (or even on a rather "ancient" PC with Intel Celeron processor).

  • Incorporation of CMA-LS-SPARSE into you own code is very simple and straightforward: all internal data structures are located inside the product. Your code just passes the matrix elements into CMA-LS-SPARSE one-by-one, together with each element's row and colulm indexes; after that you provide the system's right-hand side, and at the end CMA-LS-SPARSE will return the solution vector.

  • As soon as a brief (a few seconds) preprocessing completes, all the solution process is done completely in-core, using only the RAM and the CPU itself. Yes - up to several million of equations with sparse matrix, on your desktop or even laptop, without any use of the hard disk during the iterations !

  • The code is written in standard C and will compile/run on any platform with a standard C compiler installed.

  • Function call 1
    Function call 2
    Function call 3
    Function call 4
    Function call 5
    We invite you to consider using CMA-LS-SPARSE for your research, development and commercial purposes. You are welcome to contact us at any time, preferably by e-mail. Our full contact details are provided here .
    CMA-LS-SPARSE is available with complete source codes and with full commercial lisence allowing easy incorporation into your own applications.

    CMA-LS-SPARSE codes are written in standard C and will compile and run on all UNIX and Windows platforms without changes. They are also fully commented, allowing easy modification at user's discretion.

    CMA-LS-SPARSE is available on no-royalties and no-annual-renewals basis: there is a one-off price for an unlimited commercial lisence.

    The product distribution kit includes:

    - fully-commented source codes in C;

    - and the product's User Instructions containing decriptions of the functions and examples.

    To learn more about the full range of our products please follow this link.

    We also invite you to contact us with any questions, preferably by e-mail on or