The discretization of the stationary diffusion equation with random parameters by the Stochastic Finite Element Method requires the solution of a highly structured but very large linear system of equations. Depending on the stochastic properties of the diffusion coefficient together with the stochastic discretization we consider three solver cases. If the diffusion coefficient is given by a stochastically linear expansion, e.g. a truncated Karhunen-Loeve expansion, and tensor product polynomial stochastic shape functions are employed, the Galerkin matrix can be transformed to a block-diagonal matrix. For the solution of the resulting sequence of linear systems we study Krylov subspace recycling methods whose success depends on the ordering and grouping of the linear systems as well as the preconditioner. If we use complete polynomials for the stochastic discretization instead, we show that decoupling of the Galerkin matrix with respect to the stochastic degrees of freedom is impossible. For a stochastically nonlinear diffusion coefficient, e.g. a lognormal random field, together with complete polynomials serving as stochastic shape functions, we introduce and test the performance of a new Kronecker product preconditioner, which is not exclusively based on the mean value of the diffusion coefficient.

Hierarchical Markovian Models (HMMs) are composed of multiple low level models (LLMs) and high level model (HLM) that defines the interaction among LLMs. The essence of the HMM approach is to model the system at hand in the form of interacting components so that its (larger) underlying continous-time Markov chain (CTMC) is not generated but implicitly represented as a sum of Kronecker products of (smaller) component matrices. The Kronecker structure of an HMM induces nested block partitionings in its underlying CTMC. These partitionings may be used in block versions of classical iterative methods based on splittings, such as block SOR (BSOR), to solve the underlying CTMC for its stationary vector. Therein the problem becomes that of solving multiple nonsingular linear systems whose coefficient matrices are the diagonal blocks of a particular partitioning. This paper shows that in each HLM state there may be diagonal blocks with identical off-diagonal parts and diagonals differing from each other by a multiple of the identity matrix. Such diagonal blocks are named candidate blocks. The paper explains how candidate blocks can be detected and how the can mutually benefit from a single real Schur factorization. It gives sufficient conditions for the existence of diagonal blocks with real eigenvalues and shows how these conditions can be checked using component matrices. It describes how the sparse real Schur factors of candidate blocks satisfying these conditions can be constructed from component matrices and their real Schur factors. It also demonstrates how fill in- of LU factorized (non-candidate) diagonal blocks can be reduced by using the column approximate minimum degree algorithm (COLAMD). Then it presents a three-level BSOR solver in which the diagonal blocks at the first level are solved using block Gauss-Seidel (BGS) at the second and the methods of real Schur and LU factorizations at the third level. Finally, on a set of numerical experiments it shows how these ideas can be used to reduce the storage required by the factors of the diagonal blocks at the third level and to improve the solution time compared to an all LU factorization implementation of the three-level BSOR solver.

The discretization of the stationary diffusion equation with random parameters by the Stochastic Finite Element Method requires the solution of a highly structured but very large linear system of equations. Depending on the stochastic properties of the diffusion coefficient together with the stochastic discretization we consider three solver cases. If the diffusion coefficient is given by a stochastically linear expansion, e.g. a truncated Karhunen-Loeve expansion, and tensor product polynomial stochastic shape functions are employed, the Galerkin matrix can be transformed to a block-diagonal matrix. For the solution of the resulting sequence of linear systems we study Krylov subspace recycling methods whose success depends on the ordering and grouping of the linear systems as well as the preconditioner. If we use complete polynomials for the stochastic discretization instead, we show that decoupling of the Galerkin matrix with respect to the stochastic degrees of freedom is impossible. For a stochastically nonlinear diffusion coefficient, e.g. a lognormal random field, together with complete polynomials serving as stochastic shape functions, we introduce and test the performance of a new Kronecker product preconditioner, which is not exclusively based on the mean value of the diffusion coefficient.

Hierarchical Markovian Models (HMMs) are composed of multiple low level models (LLMs) and high level model (HLM) that defines the interaction among LLMs. The essence of the HMM approach is to model the system at hand in the form of interacting components so that its (larger) underlying continous-time Markov chain (CTMC) is not generated but implicitly represented as a sum of Kronecker products of (smaller) component matrices. The Kronecker structure of an HMM induces nested block partitionings in its underlying CTMC. These partitionings may be used in block versions of classical iterative methods based on splittings, such as block SOR (BSOR), to solve the underlying CTMC for its stationary vector. Therein the problem becomes that of solving multiple nonsingular linear systems whose coefficient matrices are the diagonal blocks of a particular partitioning. This paper shows that in each HLM state there may be diagonal blocks with identical off-diagonal parts and diagonals differing from each other by a multiple of the identity matrix. Such diagonal blocks are named candidate blocks. The paper explains how candidate blocks can be detected and how the can mutually benefit from a single real Schur factorization. It gives sufficient conditions for the existence of diagonal blocks with real eigenvalues and shows how these conditions can be checked using component matrices. It describes how the sparse real Schur factors of candidate blocks satisfying these conditions can be constructed from component matrices and their real Schur factors. It also demonstrates how fill in- of LU factorized (non-candidate) diagonal blocks can be reduced by using the column approximate minimum degree algorithm (COLAMD). Then it presents a three-level BSOR solver in which the diagonal blocks at the first level are solved using block Gauss-Seidel (BGS) at the second and the methods of real Schur and LU factorizations at the third level. Finally, on a set of numerical experiments it shows how these ideas can be used to reduce the storage required by the factors of the diagonal blocks at the third level and to improve the solution time compared to an all LU factorization implementation of the three-level BSOR solver.