|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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:
|
|
|
|
|
|
|
|
|
|
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.
|
|
|
|
|
|
|
|
|
|
A simplified (with fewer elements) model of the same panel is presented below (more images
are available on the corresponding webpage).
|
|
|
|
|
|
|
|
|
|
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.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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
comecauinfo@gmail.com.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
