Often computational time estimation for a numerical operation is based on analytic data. And the sparse matrices are often considered in engineering structural analysis. Thus, the operation counts of matrix analysis (including matrix multiply, matrix decomposition, and solution of linear systems) are often needed to be known in a analytic way. Therefore, anyone who would like to suggest some literatures and opinion are encouraged to discuss them to me.
The idea of sparse matrices is to store and compute only non-zero values in a matrix with mostly null values (like the ones generated by the finite elements method).
Computation times will then depend on how your matrix is filled (one speaks about bandwidth for example, telling how many non-zeros terms are located in each column).
For matrix multiplication you can then obtain good estimations by estimating the number of operations required for only non-zero elements.
For inversion operations, you also have to take into account the connectivity of your lines (level of dependency), that will drive the size of your factor. This is more complex to estimate, as the factorization algorithms implementation usually comes with tunable parameters that can have a huge effect on performance.
Most advanced algorithms combine a lot of concepts to achieve their performance, you can for example check out the page of the Intel MKL PARDISO librairies to get an idea
https://software.intel.com/sites/products/documentation/doclib/mkl_sa/11/mklman/GUID-7E829836-0FEF-46B2-8943-86A022193462.htm
Besides, in the context of parallel computing the performance you get will be hardware dependent as well.
A good practice is to estimate computational times of specific operations on representative matrices on your computer, from what you can extrapolate for similar types of matrices.
Most processors can do an addition, comparison or multiplication in a single cycle : those are all counted as one Flop. But division always takes longer (4 Flops in the HPC community). Flops may vary by CPU. You must know your hardware to compute the ideal Flops on the given architecture and you have to know the implementation of your algorithm it is a useful tool which tell you how you utilize the CPU. An 80387 math coprocessor took something like 300 cycles for a single multiplication. Most recently any modern intel core can perform about 2 Flops per cycle. A recent CPU will easily achieve several Giga-Flops (billion floating point operations per second). An i7 processor can perform 150 Giga-Flops. If we take exactly one second for an operation such as adding, substracting or multiplying two values the performance is simply 1 Flops (i.e 10^9 operations = 10^9 Flops). Measuring the performance of a program needs to count the number of operations. Several researchers have considered the For loop as an instruction but its real implementation takes an addition i++ and a logical test i
- Badges
- Science topic