Numerical Solvers

From Mobius Wiki
Jump to: navigation, search

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">

<xr id="table:solverSelection" nolink />: Models and measures versus the applicable numerical solvers.
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-timea 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-timeh Both diss i and adiss j
</figtable>
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 \equiv Direct Steady-State Solver
c iss \equiv Iterative Steady-State Solver
d tss \equiv Takahashi Steady-State Solver
e trs \equiv Transient Solver
f atrs \equiv Adaptive Transient Solver
g ars \equiv 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 \equiv Deterministic Iterative Steady-State Solver
j adiss \equiv 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 i 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 i 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.