×

Block SOR for Kronecker structured representations. (English) Zbl 1055.65014

Markov chain (MC) modelling with Kronecker based numerical techniques relies on representing the system at hand as a sum of Kronecker products of smaller component matrices, the explosion problem of total state space being handled by a cross product of the state spaces of the components. The present paper shows how sparse real Schur factors of certain diagonal blocks of a given partitioning induced by the Kronecker structure can be constructed from smaller component matrices and their real Schur factors. Another constructive idea is to apply the column approximate minimum degree (COLAMD) ordering algorithm as a useful tool to reduce fill-in remaining diagonal blocks that are sparse LU factorized when solving non-singular linear systems associated to MC problems.
Combining these ideas fruitfully, the authors propose a three-level block successive over-relaxation (BSOR) competitive steady state solver for hierarchical Markovian models (HMMs). HMMs are considered to be composed of multiple low level models (LLMs) and a high level model (HLM) that defines the interaction among LLMs. The Kronecker structure of a HMM induces nested block partitionings in its underlying continuous-time Markov chains (MCs). The authors show 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 called candidate blocks, and the paper explains how candidate blocks can be detected and how they can be mutually benefit from a single real Schur factorization. Sufficient conditions for the existence of diagonal blocks with real eigenvalues are given, and how to check these conditions using component matrices is detailed.
The particular implementation of the three-level BSOR solver is based on diagonal blocks at the first level, it is using block Gauss-Seidel at the second level, and the methods of real Schur and LU factorization are employed at the third level. On a set of numerical experiments, the paper demonstrates how the proposed three-level BSOR solves reduces the storage requirements and time disadvantages related to the factorization of diagonal blocks in large systems. Different combinations of parameters for the BSOR solves are experimented and comps with commonly used solvers for Kronecker representations.

MSC:

65C40 Numerical analysis or methods applied to Markov chains
60J22 Computational methods in Markov chains
65F10 Iterative numerical methods for linear systems
65F05 Direct numerical methods for linear systems and matrix inversion

Software:

COLAMD; MARCA; PEPA
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Ajmone-Marsan, M.; Donatelli, S.; Neri, F., GSPN models of Markovian multiserver multiqueue systems, Performance Evaluation, 11, 227-240 (1990)
[2] APNN-Toolbox case studies home page at http://www4.cs.uni-dortmund.de/APNN-TOOLBOX/case_studies/; APNN-Toolbox case studies home page at http://www4.cs.uni-dortmund.de/APNN-TOOLBOX/case_studies/
[3] Barret, R.; Berry, M.; Chan, T.; Demmel, J.; Donato, J.; Dongarra, J.; Eijkhout, V.; Pozo, R.; Romine, C.; van der Vorst, H., Templates for the Solution of Linear Systems (1994), SIAM Press: SIAM Press Philadelphia, Pennslyvania
[4] F. Bause, P. Buchholz, P. Kemper, A toolbox for functional and quantitative analysis of DEDS, in: R. Puigjaner, N.N. Savino, B. Serra (Eds.), Quantitative Evaluation of Computing and Communication Systems, Lecture Notes in Computer Science 1469, Springer Verlag, 1998, pp. 356-359; F. Bause, P. Buchholz, P. Kemper, A toolbox for functional and quantitative analysis of DEDS, in: R. Puigjaner, N.N. Savino, B. Serra (Eds.), Quantitative Evaluation of Computing and Communication Systems, Lecture Notes in Computer Science 1469, Springer Verlag, 1998, pp. 356-359
[5] Berman, A.; Plemmons, R. J., Nonnegative Matrices in the Mathematical Sciences (1994), SIAM Press: SIAM Press Philadelphia, Pennslyvania · Zbl 0815.15016
[6] Buchholz, P., A class of hierarchical queueing networks and their analysis, Queueing Systems, 15, 59-80 (1994) · Zbl 0789.60067
[7] Buchholz, P., Hierarchical structuring of superposed GSPNs, IEEE Transactions on Software Engineering, 95, 166-181 (1999)
[8] Buchholz, P., Structured analysis approaches for large Markov chains, Applied Numerical Mathematics, 31, 375-404 (1999) · Zbl 0934.65003
[9] Buchholz, P., Projection methods for the analysis of stochastic automata networks, (Plateau, B.; Stewart, W. J.; Silva, M., Numerical Solution of Markov Chains (1999), Prensas Universitarias de Zaragoza: Prensas Universitarias de Zaragoza Zaragoza, Spain), 149-168
[10] Buchholz, P.; Kemper, P., On generating a hierarchy for GSPN analysis, Performance Evaluation Review, 26, 5-14 (1998)
[11] Buchholz, P.; Ciardo, G.; Donatelli, S.; Kemper, P., Complexity of memory-efficient Kronecker operations with applications to the solution of Markov models, INFORMS Journal on Computing, 12, 203-222 (2000) · Zbl 1040.65504
[12] Buchholz, P.; Fisher, M.; Kemper, P., Distributed steady state analysis of stochastic automata networks, (Plateau, B.; Stewart, W. J.; Silva, M., Numerical Solution of Markov Chains (1999), Prensas Universitarias de Zaragoza: Prensas Universitarias de Zaragoza Zaragoza, Spain), 76-95
[13] Campos, J.; Donatelli, S.; Silva, M., Structured solution of asynchronously communicating stochastic modules, IEEE Transactions on Software Engineering, 25, 147-165 (1999)
[14] G. Ciardo, A.S. Miner, A data structure for the efficient Kronecker solution of GSPNs, in: P. Buchholz, M. Silva (Eds.), Proceedings of the 8th International Workshop on Petri Nets and Performance Models, IEEE-CS Press, 1999, pp. 22-31; G. Ciardo, A.S. Miner, A data structure for the efficient Kronecker solution of GSPNs, in: P. Buchholz, M. Silva (Eds.), Proceedings of the 8th International Workshop on Petri Nets and Performance Models, IEEE-CS Press, 1999, pp. 22-31
[15] COLAMD home page at http://www.cise.ufl.edu/research/sparse/colamd/; COLAMD home page at http://www.cise.ufl.edu/research/sparse/colamd/
[16] Dayar, T.; Stewart, W. J., Comparison of partitioning techniques for two-level iterative solvers on large, sparse Markov chains, SIAM Journal on Scientific Computing, 21, 1691-1705 (2000) · Zbl 0957.60076
[17] T.A. Davis, J.R. Gilbert, S.I. Larimore, E.G. Ng, A column approximate minimum degree ordering algorithm, Technical Report TR-00-005, Computer and Information Sciences Department, University of Florida, Gainesville, FL, 2000; T.A. Davis, J.R. Gilbert, S.I. Larimore, E.G. Ng, A column approximate minimum degree ordering algorithm, Technical Report TR-00-005, Computer and Information Sciences Department, University of Florida, Gainesville, FL, 2000 · Zbl 1073.65039
[18] T.A. Davis, J.R. Gilbert, S.I. Larimore, E.G. Ng, Algorithm 8xx: COLAMD, a column approximate minimum degree ordering algorithm, Technical Report TR-00-006, Computer and Information Sciences Department, University of Florida, Gainesville, FL, 2000; T.A. Davis, J.R. Gilbert, S.I. Larimore, E.G. Ng, Algorithm 8xx: COLAMD, a column approximate minimum degree ordering algorithm, Technical Report TR-00-006, Computer and Information Sciences Department, University of Florida, Gainesville, FL, 2000 · Zbl 1070.65535
[19] Demmel, J. W., Applied Numerical Linear Algebra (1997), SIAM Press: SIAM Press Philadelphia, Pennslyvania · Zbl 0879.65017
[20] Donatelli, S., Superposed stochastic automata: a class of stochastic Petri nets with parallel solution and distributed state space, Performance Evaluation, 18, 21-26 (1993) · Zbl 0795.68141
[21] Fernandes, P.; Plateau, B.; Stewart, W. J., Efficient descriptor-vector multiplications in stochastic automata networks, Journal of the ACM, 45, 381-414 (1998) · Zbl 1065.68578
[22] Fernandes, P.; Plateau, B.; Stewart, W. J., Optimizing tensor product computations in stochastic automata networks, RAIRO Operations Research, 32, 325-351 (1998)
[23] O. Gusak, T. Dayar, Iterative aggregation-disaggregation versus block Gauss-Seidel on continuous-time stochastic automata networks with unfavorable partitionings, in: M.S. Obaidat, F. Davoli (Eds.), Proceedings of the 2001 International Symposium on Performance Evaluation of Computer and Telecommunication Systems, Orlando, Florida, 2001, pp. 617-623; O. Gusak, T. Dayar, Iterative aggregation-disaggregation versus block Gauss-Seidel on continuous-time stochastic automata networks with unfavorable partitionings, in: M.S. Obaidat, F. Davoli (Eds.), Proceedings of the 2001 International Symposium on Performance Evaluation of Computer and Telecommunication Systems, Orlando, Florida, 2001, pp. 617-623
[24] Gusak, O.; Dayar, T.; Fourneau, J.-M, Lumpable continuous-time stochastic automata networks, European Journal of Operational Research, 148, 436-451 (2003) · Zbl 1035.90012
[25] S. Haddad, P. Moreaux, Asynchronous composition of high-level Petri nets: a quantitative approach, in: J. Billington, W. Reisig (Eds.), Proceedings of the 17th International Conference on Application and Theory of Petri Nets, Lecture Notes in Computer Science 1091, Springer Verlag, 1996, pp. 192-211; S. Haddad, P. Moreaux, Asynchronous composition of high-level Petri nets: a quantitative approach, in: J. Billington, W. Reisig (Eds.), Proceedings of the 17th International Conference on Application and Theory of Petri Nets, Lecture Notes in Computer Science 1091, Springer Verlag, 1996, pp. 192-211
[26] J. Hillston, L. Kloul, An efficient Kronecker representation for PEPA models, in: L. de Alfaro, S. Gilmore (Eds.), Proceedings of the 1st Process Algebras and Performance Modeling, Probabilistic Methods in Verification Workshop, Lecture Notes in Computer Science 2165, Springer Verlag, 2001, pp. 120-135; J. Hillston, L. Kloul, An efficient Kronecker representation for PEPA models, in: L. de Alfaro, S. Gilmore (Eds.), Proceedings of the 1st Process Algebras and Performance Modeling, Probabilistic Methods in Verification Workshop, Lecture Notes in Computer Science 2165, Springer Verlag, 2001, pp. 120-135 · Zbl 1007.68513
[27] Kemper, P., Numerical analysis of superposed GSPNs, IEEE Transactions on Software Engineering, 22, 615-628 (1996)
[28] Migallón, V.; Penadés, J.; Szyld, D. B., Block two-stage methods for singular systems and Markov chains, Numerical Linear Algebra with Applications, 3, 413-426 (1996) · Zbl 0906.65037
[29] Netlib, A collection of mathematical software, papers, and databases at http://www.netlib.org; Netlib, A collection of mathematical software, papers, and databases at http://www.netlib.org
[30] B. Plateau, On the stochastic structure of parallelism and synchronization models for distributed algorithms, in: Proceedings of the ACM SIGMETRICS Conference on Measurement and Modelling of Computer Systems, Austin, Texas, 1985, pp. 147-154; B. Plateau, On the stochastic structure of parallelism and synchronization models for distributed algorithms, in: Proceedings of the ACM SIGMETRICS Conference on Measurement and Modelling of Computer Systems, Austin, Texas, 1985, pp. 147-154
[31] Plateau, B.; Atif, K., Stochastic automata network for modeling parallel systems, IEEE Transactions on Software Engineering, 17, 1093-1108 (1991)
[32] Plateau, B.; Fourneau, J.-M, A methodology for solving Markov models of parallel systems, Journal of Parallel and Distributed Computing, 12, 370-387 (1991)
[33] Stewart, G. W., Matrix Algorithms, Vol II: Eigensystems (2002), SIAM Press: SIAM Press Philadelphia, Pennslyvania · Zbl 0984.65031
[34] Stewart, W. J., Introduction to the Numerical Solution of Markov Chains (1994), Princeton University Press: Princeton University Press Princeton, New Jersey · Zbl 0821.65099
[35] Uysal, E.; Dayar, T., Iterative methods based on splittings for stochastic automata networks, European Journal of Operational Research, 110, 166-186 (1998) · Zbl 0934.93061
[36] van der Vorst, H. A., BI-CGSTAB: A fast and smoothly converging variant of BI-CG for the solution of nonsymmetric linear systems, SIAM Journal on Scientific and Statistical Computing, 13, 631-644 (1992) · Zbl 0761.65023
[37] Van Loan, C. F., The ubiquitous Kronecker product, Journal of Computational and Applied Mathematics, 123, 85-100 (2000) · Zbl 0966.65039
[38] C.M. Woodside, Y. Li, Performance Petri net analysis of communications protocol software by delay equivalent aggregation, in: Proceedings of the 4th International Workshop on Petri Nets and Performance Models, IEEE CS-Press, 1991, pp. 64-73; C.M. Woodside, Y. Li, Performance Petri net analysis of communications protocol software by delay equivalent aggregation, in: Proceedings of the 4th International Workshop on Petri Nets and Performance Models, IEEE CS-Press, 1991, pp. 64-73
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.