Tuǧrul Dayar
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Tuǧrul Dayar has a total of 28 co-authors. Here are the top co-authors by number of shared publications:
M. Can Orhan
Kanava Technologies Ankara Turkey
7 shared publications- Peter Buchholz
TU Dortmund University
7 shared publications William J. Stewart
North Carolina State University, Department of Computer Science, Raleigh, North Carolina
5 shared publicationsJean-Michel Fourneau
3 shared publications- M. Can Orhan
Department of Computer Engineering, Bilkent University, TR-06800 Bilkent, Ankara, Turkey
3 shared publications Oleg Gusak
3 shared publications
Latest Publications
- 1 June 2018
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 291-302
Efficient Transient Analysis of a Class of Compositional Fluid Stochastic Petri Nets
Fluid Stochastic Petri Nets (FSPNs) which have discrete and continuous places are an established model class to describe and analyze several dependability problems for computer systems, software architectures or critical infrastructures. Unfortunately, their analysis is faced with the curse of dimensionality resulting in very large systems of differential equations for a sufficiently accurate analysis. This contribution introduces a class of FSPNs with a compositional structure and shows how the underlying stochastic process can be described by a set of coupled partial differential equations. Using semi discretization, a set of linear ordinary differential equations is generated which can be described by a (hierarchical) sum of Kronecker products. Based on this compact representation of the transition matrix, a numerical solution approach is applied which also represents transient solution vectors in compact form using the recently developed concept of a Hierarchical Tucker Decomposition. The applicability of the approach is presented in a case study analyzing a degrading software system with rejuvenation, restart, and replication.
- 1 June 2018
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 291-302
Efficient Transient Analysis of a Class of Compositional Fluid Stochastic Petri Nets
Fluid Stochastic Petri Nets (FSPNs) which have discrete and continuous places are an established model class to describe and analyze several dependability problems for computer systems, software architectures or critical infrastructures. Unfortunately, their analysis is faced with the curse of dimensionality resulting in very large systems of differential equations for a sufficiently accurate analysis. This contribution introduces a class of FSPNs with a compositional structure and shows how the underlying stochastic process can be described by a set of coupled partial differential equations. Using semi discretization, a set of linear ordinary differential equations is generated which can be described by a (hierarchical) sum of Kronecker products. Based on this compact representation of the transition matrix, a numerical solution approach is applied which also represents transient solution vectors in compact form using the recently developed concept of a Hierarchical Tucker Decomposition. The applicability of the approach is presented in a case study analyzing a degrading software system with rejuvenation, restart, and replication.
- 8 February 2018
- Published by Wiley in Numerical Linear Algebra with Applications
- Vol. 25 (5)
On compact vector formats in the solution of the chemical master equation with backward differentiation
Summary: A stochastic chemical system with multiple types of molecules interacting through reaction channels can be modeled as a continuous‐time Markov chain with a countably infinite multidimensional state space. Starting from an initial probability distribution, the time evolution of the probability distribution associated with this continuous‐time Markov chain is described by a system of ordinary differential equations, known as the chemical master equation (CME). This paper shows how one can solve the CME using backward differentiation. In doing this, a novel approach to truncate the state space at each time step using a prediction vector is proposed. The infinitesimal generator matrix associated with the truncated state space is represented compactly, and exactly, using a sum of Kronecker products of matrices associated with molecules. This exact representation is already compact and does not require a low‐rank approximation in the hierarchical Tucker decomposition (HTD) format. During transient analysis, compact solution vectors in HTD format are employed with the exact, compact, and truncated generated matrices in Kronecker form, and the linear systems are solved with the Jacobi method using fixed or adaptive rank control strategies on the compact vectors. Results of simulation on benchmark models are compared with those of the proposed solver and another version, which works with compact vectors and highly accurate low‐rank approximations of the truncated generator matrices in quantized tensor train format and solves the linear systems with the density matrix renormalization group method. Results indicate that there is a reason to solve the CME numerically, and adaptive rank control strategies on compact vectors in HTD format improve time and memory requirements significantly.
- 8 February 2018
- Published by Wiley in Numerical Linear Algebra with Applications
- Vol. 25 (5)
On compact vector formats in the solution of the chemical master equation with backward differentiation
Summary: A stochastic chemical system with multiple types of molecules interacting through reaction channels can be modeled as a continuous‐time Markov chain with a countably infinite multidimensional state space. Starting from an initial probability distribution, the time evolution of the probability distribution associated with this continuous‐time Markov chain is described by a system of ordinary differential equations, known as the chemical master equation (CME). This paper shows how one can solve the CME using backward differentiation. In doing this, a novel approach to truncate the state space at each time step using a prediction vector is proposed. The infinitesimal generator matrix associated with the truncated state space is represented compactly, and exactly, using a sum of Kronecker products of matrices associated with molecules. This exact representation is already compact and does not require a low‐rank approximation in the hierarchical Tucker decomposition (HTD) format. During transient analysis, compact solution vectors in HTD format are employed with the exact, compact, and truncated generated matrices in Kronecker form, and the linear systems are solved with the Jacobi method using fixed or adaptive rank control strategies on the compact vectors. Results of simulation on benchmark models are compared with those of the proposed solver and another version, which works with compact vectors and highly accurate low‐rank approximations of the truncated generator matrices in quantized tensor train format and solves the linear systems with the density matrix renormalization group method. Results indicate that there is a reason to solve the CME numerically, and adaptive rank control strategies on compact vectors in HTD format improve time and memory requirements significantly.
- 25 January 2018
- Published by Springer Nature
- p. 312-316
A Software Tool for the Compact Solution of the Chemical Master Equation
- 25 January 2018
- Published by Springer Nature
- p. 312-316
A Software Tool for the Compact Solution of the Chemical Master Equation
- 1 January 2018
- Published by Springer Nature
Kronecker Modeling and Analysis of Multidimensional Markovian Systems
- 1 January 2018
- Published by Springer Nature
Kronecker Modeling and Analysis of Multidimensional Markovian Systems
- 1 October 2017
- Published by Elsevier in Performance Evaluation
- Vol. 115, 132-149
On compact solution vectors in Kronecker-based Markovian analysis
- 1 October 2017
- Published by Elsevier in Performance Evaluation
- Vol. 115, 132-149
On compact solution vectors in Kronecker-based Markovian analysis
- 9 December 2016
- Published by Cambridge University Press (CUP) in Journal of Applied Probability
- Vol. 53 (4) , 1098-1110
Steady-state analysis of a multiclass MAP/PH/cqueue with acyclic PH retrials
A multiclassc-server retrial queueing system in which customers arrive according to a class-dependent Markovian arrival process (MAP) is considered. Service and retrial times follow class-dependent phase-type (PH) distributions with the further assumption that PH distributions of retrial times are acyclic. A necessary and sufficient condition for ergodicity is obtained from criteria based on drifts. The infinite state space of the model is truncated with an appropriately chosen Lyapunov function. The truncated model is described as a multidimensional Markov chain, and a Kronecker representation of its generator matrix is numerically analyzed.
- 9 December 2016
- Published by Cambridge University Press (CUP) in Journal of Applied Probability
- Vol. 53 (4) , 1098-1110
Steady-state analysis of a multiclass MAP/PH/cqueue with acyclic PH retrials
A multiclassc-server retrial queueing system in which customers arrive according to a class-dependent Markovian arrival process (MAP) is considered. Service and retrial times follow class-dependent phase-type (PH) distributions with the further assumption that PH distributions of retrial times are acyclic. A necessary and sufficient condition for ergodicity is obtained from criteria based on drifts. The infinite state space of the model is truncated with an appropriately chosen Lyapunov function. The truncated model is described as a multidimensional Markov chain, and a Kronecker representation of its generator matrix is numerically analyzed.
- 3 August 2016
- Published by Springer Nature
- p. 260-276
Compact Representation of Solution Vectors in Kronecker-Based Markovian Analysis
- 3 August 2016
- Published by Springer Nature
- p. 260-276
Compact Representation of Solution Vectors in Kronecker-Based Markovian Analysis
- Open Access
- 18 May 2016
- Published by Cambridge University Press (CUP) in Probability in the Engineering and Informational Sciences
- Vol. 30 (3) , 413-430
CARTESIAN PRODUCT PARTITIONING OF MULTI-DIMENSIONAL REACHABLE STATE SPACES
Markov chains (MCs) are widely used to model systems which evolve by visiting the states in their state spaces following the available transitions. When such systems are composed of interacting subsystems, they can be mapped to a multi-dimensional MC in which each subsystem normally corresponds to a different dimension. Usually the reachable state space of the multi-dimensional MC is a proper subset of its product state space, that is, Cartesian product of its subsystem state spaces. Compact storage of the matrix underlying such a MC and efficient implementation of analysis methods using Kronecker operations require the set of reachable states to be represented as a union of Cartesian products of subsets of subsystem state spaces. The problem of partitioning the reachable state space of a three or higher dimensional system with a minimum number of partitions into Cartesian products of subsets of subsystem state spaces is shown to be NP-complete. Two algorithms, one merge based the other refinement based, that yield possibly non-optimal partitionings are presented. Results of experiments on a set of problems from the literature and those that are randomly generated indicate that, although it may be more time and memory consuming, the refinement based algorithm almost always computes partitionings with a smaller number of partitions than the merge-based algorithm. The refinement based algorithm is insensitive to the order in which the states in the reachable state space are processed, and in many cases it computes partitionings that are optimal.
- 18 May 2016
- Published by Cambridge University Press (CUP) in Probability in the Engineering and Informational Sciences
- Vol. 30 (3) , 413-430
Open AccessCARTESIAN PRODUCT PARTITIONING OF MULTI-DIMENSIONAL REACHABLE STATE SPACES
Markov chains (MCs) are widely used to model systems which evolve by visiting the states in their state spaces following the available transitions. When such systems are composed of interacting subsystems, they can be mapped to a multi-dimensional MC in which each subsystem normally corresponds to a different dimension. Usually the reachable state space of the multi-dimensional MC is a proper subset of its product state space, that is, Cartesian product of its subsystem state spaces. Compact storage of the matrix underlying such a MC and efficient implementation of analysis methods using Kronecker operations require the set of reachable states to be represented as a union of Cartesian products of subsets of subsystem state spaces. The problem of partitioning the reachable state space of a three or higher dimensional system with a minimum number of partitions into Cartesian products of subsets of subsystem state spaces is shown to be NP-complete. Two algorithms, one merge based the other refinement based, that yield possibly non-optimal partitionings are presented. Results of experiments on a set of problems from the literature and those that are randomly generated indicate that, although it may be more time and memory consuming, the refinement based algorithm almost always computes partitionings with a smaller number of partitions than the merge-based algorithm. The refinement based algorithm is insensitive to the order in which the states in the reachable state space are processed, and in many cases it computes partitionings that are optimal.
- 1 January 2015
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Scientific Computing
- Vol. 37 (5) , S526-S543
On Vector-Kronecker Product Multiplication with Rectangular Factors
The infinitesimal generator matrix underlying a multidimensional Markov chain can be represented compactly by using sums of Kronecker products of small rectangular matrices. For such compact representations, analysis methods based on vector-Kronecker product multiplication need to be employed. When the factors in the Kronecker product terms are relatively dense, vector-Kronecker product multiplication can be performed efficiently by the shuffle algorithm. When the factors are relatively sparse, it may be more efficient to obtain nonzero elements of the generator matrix in Kronecker form on the fly and multiply them with corresponding elements of the vector. This work proposes a modification to the shuffle algorithm that multiplies relevant elements of the vector with submatrices of factors in which zero rows and columns are omitted. This approach avoids unnecessary floating-point operations that evaluate to zero during the course of the multiplication and possibly reduces the amount of memory used. Numeri...
- 1 January 2015
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Scientific Computing
- Vol. 37 (5) , S526-S543
On Vector-Kronecker Product Multiplication with Rectangular Factors
The infinitesimal generator matrix underlying a multidimensional Markov chain can be represented compactly by using sums of Kronecker products of small rectangular matrices. For such compact representations, analysis methods based on vector-Kronecker product multiplication need to be employed. When the factors in the Kronecker product terms are relatively dense, vector-Kronecker product multiplication can be performed efficiently by the shuffle algorithm. When the factors are relatively sparse, it may be more efficient to obtain nonzero elements of the generator matrix in Kronecker form on the fly and multiply them with corresponding elements of the vector. This work proposes a modification to the shuffle algorithm that multiplies relevant elements of the vector with submatrices of factors in which zero rows and columns are omitted. This approach avoids unnecessary floating-point operations that evaluate to zero during the course of the multiplication and possibly reduces the amount of memory used. Numeri...
- 1 September 2013
- Published by Elsevier in Performance Evaluation
- Vol. 70 (9) , 663-681
On the numerical solution of Kronecker-based infinite level-dependent QBD processes
- 1 September 2013
- Published by Elsevier in Performance Evaluation
- Vol. 70 (9) , 663-681
On the numerical solution of Kronecker-based infinite level-dependent QBD processes