Analyzing Markov Chains using Kronecker Products: Theory and Applications

محصولات کرونکر برای تعریف زنجیره مارکوف زیربنایی (MC) در فرمالیسم‌های مختلف مدل‌سازی، از جمله مدل‌های مارکوفی ترکیبی، مدل‌های مارکوی سلسله مراتبی، و جبرهای فرآیند تصادفی استفاده می‌شوند. انگیزه پشت استفاده از نمایش ساختار یافته کرونکر به جای یک نمایش مسطح، کاهش نیازهای ذخیره سازی مرتبط با MC است. با این رویکرد، سیستم هایی که مرتبه ای بزرگتر هستند را می توان بر روی یک پلت فرم تجزیه و تحلیل کرد. پیشرفت‌ها در حل چنین MC‌هایی از دیدگاه جبری بررسی می‌شوند و زمینه‌های احتمالی برای تحقیقات بیشتر با تأکید بر پیش پردازش با استفاده از مرتب‌سازی مجدد، گروه‌بندی، و توده‌بندی و تجزیه و تحلیل عددی با استفاده از تکرار بلوکی، طرح پیش‌شرطی، چند سطحی، تجزیه، و روشهای تحلیل ماتریسی مطالعات موردی از شبکه‌های صف بسته و سینتیک‌های شیمیایی تصادفی به ترتیب برای ایجاد انگیزه در روش‌های تجزیه و تحلیل ماتریسی ارائه شده‌اند.

Kronecker products are used to define the underlying Markov chain (MC) in various modeling formalisms, including compositional Markovian models, hierarchical Markovian models, and stochastic process algebras. The motivation behind using a Kronecker structured representation rather than a flat one is to alleviate the storage requirements associated with the MC. With this approach, systems that are an order of magnitude larger can be analyzed on the same platform. The developments in the solution of such MCs are reviewed from an algebraic point of view and possible areas for further research are indicated with an emphasis on preprocessing using reordering, grouping, and lumping and numerical analysis using block iterative, preconditioned projection, multilevel, decompositional, and matrix analytic methods. Case studies from closed queueing networks and stochastic chemical kinetics are provided to motivate decompositional and matrix analytic methods, respectively.