5.6 MAMSolver

MAMSOLVER is a software tool that provides efficient implementations of the state-of-the-art algorithms of the matrix-analytic methodology including the matrix-analytic and matrix-geometric solution techniques for M/G/1-type and GI/M/1-type processes, respectively. MAMSOLVER also provides an implementation of the ETAQA methodology. Although, this exposition of matrix-analytic methods and ETAQA considers only CTMCs, MAMSOLVER provides solutions for both DTMCs and CTMCs.

The matrix-analytic algorithms that we take into consideration are defined in terms of matrices, making matrix manipulations and operations the basic elements of the tool. The input to MAMSolver, in the form of a structured text file, is the finite set of matrices that accurately describe the process to be solved. Since there are different algorithms that provide solution for the same process, the user specifies the method to be used. However, several tests are performed within the tool to insure that special cases are treated separately and therefore more efficiently. MAMSOLVER is implemented in C++, and classes define the basic components of the type of processes under consideration.

Matrix is the module that implements all the basic matrix operations such as matrix assignments, additions, subtractions, multiplications, and inversions. For computational efficiency, we use well known and heavily tested routines provided by the Lapack and BLAS packages^5.5. Since solving a finite system of linear equations is a core function in matrix-analytic algorithms, MAMSolver provides several numerical methods depending on the size of the problem, i.e., the size of the coefficient matrices. For small-size problems exact methods such as LU-decomposition are used, otherwise the Lapack implementation of iterative methods such as GMRES and BiCGSTAB, are chosen.

Matrix-analytic modules handle both CTMC and DTMC processes. First these modules provide storage for the input matrices. In addition, these modules provide all the routines necessary for the implementation of the algorithms outlined in Chapter 3. Both the data structures and routines of the matrix-analytic modules are based on the data-structures and routines provided by the matrix module. The high-level structure of MAMSOLVER is illustrated in Figure 5.6.

Figure 5.6: MAMSolver structure

The solution of QBD processes, requires computation of the ${\mathbf{R}}$ (and sometimes of ${\mathbf{G}}$ depending on the solution algorithm). First the matrix ${\mathbf{R}}$ is computed using the logarithmic reduction algorithm[47]. For completeness, we provide also the classic numerical algorithm. To guarantee that there is no expensive (and unnecessary) iterative computation of ${\mathbf{G}}$ (and ${\mathbf{R}}$), the tool first checks if the conditions for explicit computation hold [77]. The available solution methods for QBD processes are matrix-geometric and ETAQA-QBD.

GI/M/1 processes require the computation of the matrix ${\mathbf{R}}$. The classic matrix geometric solution is implemented to solve this type of processes. First the algorithm goes through a classic iterative algorithm to compute ${\mathbf{R}}$ (to our knowledge, there is no alternative more efficient than the classic algorithm). Then, the tool computes the boundary part of the stationary probability vector. Since a geometric relation exist between vectors $\mbox{\boldmath {$\pi$}}^{(i)}$ for $i \geq 1$, there is no need to compute the whole stationary probability vector.

M/G/1 processes require the computation of the matrix ${\mathbf{G}}$ which is calculated using the classic iterative algorithm or the cyclic-reduction algorithm or the explicit one (if applied). The stationary probability vector is computed recursively using either the recursive Ramaswami formula or its fast FFT version. ETAQA-M/G/1 is also implemented as an alternative for the solution of M/G/1 processes. A brief summary of the most important matrix-analytic algorithms implemented in MAMSOLVER is depicted in Figure 5.7.

Figure 5.7: MAMSolver algorithms