Takahashi Steady-State Solver

From Mobius Wiki
Jump to: navigation, search

Takahashi steady-state solver

The Takahashi steady-state solver (tss) solves for instant-of-time variables with t \rightarrow \infty. It is an iterative solver meaning that it initially guesses an initial value for the \pi vector (state occupancy probability), and then at each iteration, it computes a new value for \pi that may be “closer” to the value that satisfies \pi Q = 0. For the Takahashi solver, the initial guess for \pi is equal probabilities for all states.

The solver is an instance of a general class of iterative solvers called IAD (Iterative Aggregation/Disaggregation) solvers[1]. In IAD solvers, the Q matrix is partitioned into N \times N blocks. As their names imply, each (main) iteration of the solution algorithm of IAD solvers is comprised of two phases: 1) aggregation and 2) disaggregation.

In the first phase, an N \times N aggregation matrix A is constructed by computing each of its elements from the corresponding block of Q. Then, the system of equations \xi A = \xi is solved using the SOR iterative steady-state solver (see Section 4.3.3) to compute the vector \xi. In the second phase, N systems of equations each of which derived from a column of N blocks of Q are solved by the SOR solver. Based on the solution vectors computed in the two phases, a new value for \pi is computed. The iterations are repeated until either the maximum difference between the elements of the previous \pi and the new \pi is less than a given error boundary (given by the Accuracy parameter described below) or the number of iterations exceeds a given maximum value (given by the Max Iterations parameter described below).

Because of its more modest space requirements, this solver can be applied to larger models than dss can, but it is not guaranteed to converge for all state spaces and initial conditions. It calculates the mean and variance for each performance variable. The means and variances are recorded in textual format in an output file. <xr id="fig:tssSolver" /> shows the editor for the Takahashi steady-state solver and its available options and adjustable parameters.


<figure id="fig:tssSolver">

SolverTSS.png


<xr id="fig:tssSolver" nolink />: Takahashi Steady-State Solver (tss) editor and available options and parameters.
</figure>


The options are as follows:

  • The Number of Divisions is the positive integer N mentioned above. Default value is 5.
  • The Accuracy determines the accuracy used for checking convergence condition on \pi. Default value is 9. See Section 4.3.1.
  • The Max Iterations is an integer representing the maximum number of main iterations that will be performed before the solver terminates. Default value is 300,000.
  • The Aggregation Phase Accuracy is the accuracy of the iterative SOR solver of the aggregation phase. Default value is 9.
  • The Aggregation Phase Max Iterations is an integer representing the maximum number of iterations (for each main iteration of the tss solver) that the SOR solver of the aggregation phase performs before it terminates. Default value is 300,000.
  • The Aggregation Phase Weight is a double representing the acceleration factor for the SOR solution of the aggregation phase. 0.95 is the default. See Section 4.3.3 for more information.
  • The Disaggregation Phase Accuracy is the same as Aggregation Phase Accuracy except that it is used in disaggregation phase of each main iteration.
  • The Disaggregation Phase Max Iterations is the same as Aggregation Phase Max Iterations except that it is used in disaggregation phase of each main iteration.
  • The Disaggregation Phase Weight is the same as Aggregation Phase Weight except that it is used in disaggregation phase of each main iteration.
  • The Verbosity (n) sets the trace level of intermediate output. The default is no intermediate output. If n > 0, then some details about the progress of the solution algorithm is printed out. n >=2 is more verbose than n = 1.


Pitfalls and Hints

  • This solver is most suitable for NCD (Nearly Completely Decomposable) Markov chains[1]. An NCD Markov chain is one whose state space can be partitioned into disjoint subsets such that the transition rates among states of the same subset are relatively high and among states of different subsets are relatively low.
  • In the current version of Möbius, the Takahashi solver is applicable to state spaces generated from the flat state-space generator but not to ones generated from the symbolic state-space generator. The reason is that a generator matrix can be divided into blocks in a straightforward manner when it is represented as a sparse matrix but that it is not the case when it is represented symbolically.
  • Currently, Möbius does not apply any particular automatic method to compute the optimum value for N, to compute the optimum size of the blocks, or to determine the best reordering of the states. The reason is that optimizing each of those parameters is, in some cases, more difficult than the solution of the Markov chain itself, if not intractable.

References

  1. 1.0 1.1 W. J. Stewart. Introduction to the Numerical Solution of Markov Chains. Princeton University Press, 1994.