Numerical Solvers
Contents
Numerical Solvers
This section discusses the numerical (or analytic) solvers that are supported in Möbius. A number of solvers are available for computing solutions to various types of performability measures. This chapter begins by explaining how a new solver can be created. It then gives guidelines for choosing the appropriate solver for a given model class and measures of interest. Finally, it discusses in detail all of the available solvers and their relevant parameters. The discussion of each solver includes tips on pitfalls to avoid and hints for effective use of the solver.
Creating a New Numerical Solver
All of the solvers presented in this chapter compute their solutions by analyzing the underlying state space of a model. The state space is generated using the state space generator, as described in Section 2.2. You can create a new numerical solver by selecting Numerical on the Project panel and clicking the button New. A dialog window will appear, requesting a name and the type of solver to use. After you have entered the name and chosen the type of solver, a dialog appears, requesting the name of the state space to be analyzed. You can choose the desired state space by clicking on one of the choices presented in the dialog window Select Numerical Child. After you select the state space, the main editor for the numerical solver appears. You use the editor to enter the relevant parameters for your solver. The parameters corresponding to each solver are explained in the sections below. After a solver has been created, you can open it for revision by simply double-clicking on its name or by selecting its name and clicking the Open button on the Project panel.
Choosing the Appropriate Numerical Solver
The choice of which numerical solver to use depends on the type of a solvable model and the type of performability measures of interest. The type of a solvable model is determined by the distributions of its actions (see Section 1.2.5 of Modeling Background for an explanation of the numerous distributions supported by Möbius). A solvable model may be one of two types:
- Markov Model: All timed actions in models of this type are exponentially distributed.
- Deterministic Model: Timed actions in models of this type may be a mixture of exponential and deterministic distributions. However, there can be no more than one enabled deterministic action at any time, and the time of the deterministic activity cannot depend on the marking of the model.
A performability measure has three defining attributes. These attributes, together with the model type, determine the appropriate solver to use. They are as followings:
- Whether the performability measure is obtained in transient or steady state;
- Whether the performability measure is measured at an instant of time or over an interval of time;
- Whether the mean, variance, or both are desired.
The selection of an appropriate solver based on these attributes and model type is summarized in <xr id="table:solverSelection" />. In addition, a list of advantages and disadvantages in using the numerical solvers is provided below. You should consider these issues in order to make effective use of the solvers.
<figtable id="table:solverSelection">
NUMERICAL SOLVERS (FOR REWARD VARIABLES ONLY) | ||||
Model Class | Steady-state
or Transient |
Instant-of-time
or Interval-of-time |
Mean,
Variance, or Both |
Applicable
Analytic Solver |
---|---|---|---|---|
All actions
exponential |
Steady-state | Instant-of-time^{a} | Both | dss ^{b}, iss ^{c}, and tss ^{d} |
Transient | Instant-of-time | Both | trs ^{e} and atrs ^{f} | |
Interval-of-time | Mean | ars ^{g} | ||
Exponential and
deterministic actions |
Steady-state | Instant-of-time^{h} | Both | diss ^{i} and adiss ^{j} |
^{a} if only rate rewards are used, the time-averaged interval-of-time steady-state measure is identical to the instant-of-time steady-state measure (if both exist). |
^{b} dss Direct Steady-State Solver |
^{c} iss Iterative Steady-State Solver |
^{d} tss Takahashi Steady-State Solver |
^{e} trs Transient Solver |
^{f} atrs Adaptive Transient Solver |
^{g} ars Accumulated Reward Solver |
^{h} provided that the instant-of-time steady-state distribution is well-defined. Otherwise, the time-averaged interval-of-time steady-state variable is computed, and only results for rate rewards should be derived. |
^{i} diss Deterministic Iterative Steady-State Solver |
^{j} adiss Advanced Deterministic Iterative Steady-State Solver |
Advantages of analytic solution
- Exact computation of solution is carried out, as opposed to simulation, in which the solution is estimated along with a confidence interval indicating how likely it is that the estimated solution is the solution of the exact computation.
- For the instant-of-time performability variables, distributions can be obtained without extra cost beyond that of obtaining their mean and variance.
- Accuracy of the solution can, for most solvers, be increased without excessive increase in the computation time (within the limitations stemming from machine accuracy).
Disadvantages of analytic solution
- Analytic solvers are not available for all models. The models must belong to one of the two model classes discussed above.
- The state space size of the generated model must be finite. Moreover, it cannot be too large relative to the memory of the computer being used. The iterative solvers iss, trs, and ars can usually deal with models having several million states. The other solvers demand additional memory on top of that needed for the storage of the transition matrix. See the discussion in the sections specific to the different solvers for more details.
- It is a challenge to create models from which all the desired performability results can be derived, but which have a state space small enough to allow for analytic solution. Considerable payoffs can be expected from exploring state space reduction approaches. In that respect, the use of the Rep construct in the composed model can be very helpful.
- Analytic solution is time-consuming if one is dealing with stiff models. A prominent class of stiff models is the one with a wide range of expected action completion times. An example is a dependability model in which there are long periods until component failures and relatively fast repairs.
Additional constraints
In addition to the constraints already imposed on the two model classes discussed above, analytic solvers of either class cannot be used to solve PEPA models which contain guard conditions.
Detailed Descriptions of Supported Numerical Solvers
The technical details of the supported numerical solvers are described below. Details are given about how their required parameters are entered into Möbius and how their output should be interpreted. The discussion includes hints on pitfalls to avoid and ways to make effective use of the solvers.
Common options among all analytic solvers
The following options are common to all the solvers:
- Accuracy is an integer indicating the degree of accuracy that the user wishes in terms of the number of digits to the right of the decimal point. Usually, the default is nine digits. If the number of digits specified exceeds the machine accuracy, then the machine accuracy is used. Note that the precise meaning of the accuracy setting depends on the solver. The precise meaning of Accuracy will be stated in the below discussion of the individual solvers.
- The State Space Name specifies the generated state space to use for computing numerical solutions. You may choose among the available state spaces by pressing the button “...” to the right of the text field next to State Space Name.
- If an Output File Name is given as (for example) “outfile”, the results are written into the file outfile_Experiment_i.txt, where is the experiment number. This file is put in the solver’s results directory, MobiusProject/projectname/Result/solvername. If no output file is given, the output goes to the control panel window.
- If a Debug File Name is given as (for example) “debugfile”, debug information is written into the file debugfile_Experiment_i_debug.txt, where is the experiment number. This file is put in the solver’s results directory, MobiusProject/projectname/Result/solvername. If no debug file is given, no debug information is generated. The debug information consists essentially of detailed information regarding the solver. It can be useful for determining whether a solution converges, but usually the same information can be obtained more naturally by setting the Verbosity. The Verbosity option will be discussed with respect to each individual solver.
- Plot Complementary Distribution is not currently supported by Möbius.
- If Run in the Background is selected, the solver process is run in the background so that other control panel options can still be used while the solver is running. If no output file is specified, output automatically goes to the control panel window.
The output file of each solver contains various information. It first itemizes the options that were used, including defaults, and it contains the results of the solution process. It also records the following information:
- The project, study, and experiment for which the results were computed.
- The Global variable settings, which are the values assigned to all the global variables in the chosen experiment.
- The Number of states in process, which is the number of states that were generated by the state-space generator.
- The Number of non-zero elements, which is the number of non-zero elements in the transition matrix.
- The Computation Time, which is the total execution time, equal to the sum of user time and system time.
- The User Time, which is the total amount of time spent executing in user mode.
- The System Time, which is the total amount of time spent executing in system mode.