Mathematical Toeplitz Package for E-MicroM manages the matrix vector product for Multi levels Toeplitz matrix. A toeplitz matrix is a matrix whose value at element at row i and j depends only on i-j. A multi-level toeplitz matrix is a matrix whose block is toeplitz matrix. Each block is also a toeplitz matrix. More...
Mathematical Toeplitz Package for E-MicroM manages the matrix vector product for Multi levels Toeplitz matrix. A toeplitz matrix is a matrix whose value at element at row i and j depends only on i-j. A multi-level toeplitz matrix is a matrix whose block is toeplitz matrix. Each block is also a toeplitz matrix.
![$ T = \left[ {\begin{array}{ccccc} T^k_0 & T^k_{-1} & T^k_{-2} & ... & T^k_{1-n_k} \\ T^k_1 & T^k_0 & ... & ... & T^k_{2-n_k} \\ ... & ... & ... & ... & ... \\ T^k_{n_k-1} & T^k_{n_k-2} & ... & ... & T^k_0 \end{array} } \right] $](form_1930.png)
The description of a toeplitz matrix is in the class MATH_MultiLevelsToeplitzMatrix.
The main avantage of a toeplitz matrix is that the Matrix Vector product cost is in N.log(N) due to a diagonalization of this matrix thant to a Discret Fourier Transform. see FFTW library interface package . The projection in the spectral space and the matrix vector product are managed in the general interface class MATH_MultiLevelsToeplitzMatrix which have 4 implementations of the product by FFT method:
- MATH_GlobalMultiLevelsPolynomialToeplitzMatrix to project in a large spectral space composed by all the values of the matrix and use the convolution of polynoms to compute the Matrix vector product when the multi-levels Toeplitz matrix is turned into a 1-level toeplitz matrix.
- MATH_ElementaryMultiLevelsPolynomialToeplitzMatrix to project each element of a leaf block matrix in its own spectral space and use the convolution of polynoms to compute the Matrix vector product when the multi-levels Toeplitz matrix is turned into a 1-level toeplitz matrix.
- MATH_ElementaryMultiLevelsCircularToeplitzMatrix to project each element of a leaf block matrix in its own spectral space and use the matrix vector product for circular matrix when the multi-levels Toeplitz matrix is turned into a 1-level toeplitz matrix.
- MATH_ElementaryMultiLevelsCircularTensorToeplitzMatrix to project each element of a leaf block matrix in its own spectral space and use the matrix vector product for circular matrix for each level.
The MATH_ToeplitzClassFactory manages the creation of classes of the package.
The MATH_ToeplitzRun is the main class of the package.
The MATH_ToeplitzTest is the class test of the package.
To compare the different methods, a 3 levels toeplitz matrix is built with a full storage for leaf for the Global Multi levels based on polynomial covolution (GP) and a packed storage for the other methods.
- GP designed a Toeplitz Matrix Vector product based on a 1-level FFT polynomial covolution on all the 3D vector values.
- LT designed a Toeplitz Matrix Vector product based on a multi-levels FFT Circular matrix vector product for the values of the 3D-vector per each coordinates.
- LC designed a Toeplitz Matrix Vector product based on a 1-level FFT Circular matrix vector product for the values of the 3D-vector per each coordinates.
- LP designed a Toeplitz Matrix Vector product based on a 1-level FFT polynomial covolution for the values of the 3D-vector per each coordinates.
we use the different grid of size Nx x Ny x Nz, the demagnetized operator is discretized on the grid and the projection of the spectral spaces is done for each different method. Then , 100 matrix product vector is computed and we compare the results with the openmp version of 4 threads:
| Nx | Ny | Nz | N |
| 4 | 4 | 4 | 64 |
| 8 | 8 | 8 | 512 |
| 16 | 16 | 16 | 4 096 |
| 32 | 32 | 32 | 32 768 |
| 64 | 64 | 64 | 262 144 |
The result is as follow and the best methods is the LC/LP methods which are equivalents.
 |
| discretization (ms) |
 |
| 100x matrix vector product (ms) |
 |
| memory size (Kb) |
The uml graph is as follow:
