Computational Mechanics Australia Pty Ltd
The Company Products Contact
CMA-SPARSE
CMA-SPARSE: Solver of Systems of Linear Algebraic Equations with Very Large Sparse Matrices.
Obtaining numerical solutions of partial differential equations using the Finite Difference or Finite Element Method inevitably brings up a necessity to solve systems of linear algebraic equations with very large, sparse matrices.

How actually large is "large" ? Several tens of thousands of equations is a pretty ordinary system for modern computers. However, real-life problems arising from the use of PDE, especially three-dimensional, can lead to systems with much larger matrices. Two or three million equations, involving a sparse matrix, do represent a problem, unless you have an access to a computer somewhat more powerful than an ordinary desktop.

But you still can use your ordinary desktop computer to solve such system. Our company has developed a special software program for that: CMA-SPARSE - our company's newest product.

CMA-SPARSE is an absolutely unique tool, suitable for solving very large (up to several million equations) sparse linear systems with symmetric positive definite matrices. 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-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-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-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.

  • In case if your application is developed in the Microsoft Visual C/C++ environment, you may also activate, during the compilation statge, a number of parallel processing algorithms. It is just a single #define command in the CMA-SPARSE codes that activates corresponing additional algorithms, to make computations faster than the original sequential algorithm.

  • A more advanced version of CMA-SPARSE, also allows systems with multiple right-hand sides.

  • On a more technical side, the following example demonstrates the program's capabilites.

    Consider calculation of deflections of a perforated panel using the Finite Element Method. Our accurate and efficient FEA product QUAD-PLATE has been used for that purpose. The model presented here is a square-shaped panel, with two (vertical) edges clamped and a distributed lateral pressure applied to each finite element. The panel contains a set of 70 openings. The finite element model has the following properties:
    Panel 1 data
    We selected this particular example for a purpose. It is known that iterative processes converge faster or slower depending on the matrix spectral properties. Thin-walled structures are notoriously known as having rather ill-conditioned matrices, which can make the convergence slow. Nevertheless, CMA-SPARSE has demonstrated excellent performance.

    The above figure represents the actual size of the system of linear algebraic equations that has been solved by CMA-SPARSE. All technical parameters of the computer used and the obtained results are presented below.
    Panel 1 system of linear equations and performance data
    A simplified (with fewer elements) model of the same panel is presented below (more images are available on the corresponding webpage).
    Mesh of perforated panel
    In order to demonstrate the influence of the matrix spectral properties on the convergence, we also run the same model but this time prepared for a thick plate: the thickness was selected to be 40 mm instead of three (the lateral load was also increased to 10^5 N/m^2). In this case the convergence to solution was achieved in just 1 min. 45 sec. !

    Why the above comparison is important ? The Finite Element Method is often used for the analysis of three-dimensional models consisting of tetrahedral and/or hexahedral elements. It turned out that the spectral properties of the corresponding stiffness matrices demonstrate behavior similar to the second case from the above. The difference is that the average number of non-zero elements per column under the principal diagonal of the matrix is about twice as much: about 25 (plus or minus a few, depending on the actual finite element used). In this case, the advantages of CMA-SPARSE are even more pronounced: due to the fact that CMA-SPARSE contains not only sequential implementation of the algorithm, but also a parallel implementation, the solution can be obtained much faster; the CPU time savings may be from 15% to 50% (depending on the parameters of actual CPU, which include the size of cache memory).

    Our next example is a perforated panel similar to the previous one, but with significantly larger number of quadrilateral elements. This time the model has twenty rows and twenty five columns of openings.
    Panel 25x20
    Panel 25x20 left top corner
    Panel 25x20 left top corner
    This problem was aslo solved by CMA-SPARSE; results are presented above. It is interesting to note that this time the convergence rate (which is assumed to be a ratio between the number of equations and the number of iterations performed for convergence) was much higher than in the previous example. As mentioned before, after a number of additional numerical experiments we found that the principal contributing factor was the panel thickness: modeling of thick plates by Mindlin elements leads to the stiffness matrices with significantly better spectral properties than modeling of thin plates, when the matrices can have relatively large condition ratios, leading to slower convergence of the iterations.

    A special version for systems of linear equations with multiple right-hand sides.
    But there is more to CMA-SPARSE than the ability to solve very large systems. It is a common occurence that a particular system of equations with one and the same matrix may have multiple right-hand sides; for example, one and the same finite element model can be subjected to a variety of different loads, thus leading to solve the system several times. This is not a problem for direct (for example, the Cholessky's) methods; but the amount memory required to store matrices of linear systems containing millions of equations, makes it impossible to use direct methods for such systems on ordinary computers.

    Iterative methods can solve very large problems, as demonstrated above, but the iterations must be performed every time all over again, for each right-hand side. In order to tackle that problem, we developed an extended version of CMA-SPARSE, named CMA-SPARSE-MULTIPLE-RHS. This product can solve, at the same time, several systems of linear equations with different right-hand sides, and relies on the use of a variety of parallel programming technologies supported by the MSVC development environment (the codes are still written in C). As a result, each additional right-hand side increases the CPU time not by 100%, but by less than 40% only (compared to the solution time required by the standard, single right-hand side solver, implemented in the CMA-SPARSE). CMA-SPARSE-MULTIPLE-RHS is very flexible in terms of the use of multicore and/or multi-processor computers: it allows simultaneous solution of any number of systems of linear equations with one and the same matrix and different right-hand sides, provided the computer has sufficient resourses to store the additional RHS and the solution vectors in the Random-Access Memory.

    We invite you to consider using CMA-SPARSE and CMA-SPARSE-MULTIPLE-RHS 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-SPARSE and CMA-SPARSE-MULTIPLE-RHS are available with complete source codes and with the full commercial lisence allowing easy incorporation into your own applications.

    CMA-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-SPARSE-MULTIPLE-RHS codes are written in C with the use of parallelization routines impelemented in standard Microsoft Visual C development environment. The codes will compile and run on Windows platforms with MSVC installed, including free products like Microsoft Visual C/C++ 2009 Express Edition, which can be downloaded directly from the Microsoft website.

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

    Both products' distribution kits include:

    - fully-commented source codes in C;

    - and the products' 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 comecau@ozemail.com.au or comecau1@bigpond.net.au.