×

Identification of almost invariant aggregates in reversible nearly uncoupled Markov chains. (English) Zbl 0963.65008

The paper is devoted to a model identification problem, rising from a concrete application task. The key idea is to synthesize an algorithm for identification of almost invariant componentwise aggregates, via the sign structure of the eigenvectors corresponding to the Perron cluster of eigenvalues.
Based on the latest results in the area of reversible uncoupled Markov chains, a particular discriminating sign structure is derived, for the identification of invariant aggregates. A robust identification algorithm is derived. Part of it is transformed into a solution of the graph coloring problem, which is known as NP-complete. As a consequence, heuristics are justified to play a crucial role in the computational solution and algorithm implementation.
Two examples are given, to illustrate the performance of the suggested identification algorithm. One of them is simple artificial but the second concerns molecular dynamics and particular detection of the known chemical structure, without explicit use of chemical insight.

MSC:

65C40 Numerical analysis or methods applied to Markov chains
60J22 Computational methods in Markov chains
80A30 Chemical kinetics in thermodynamics and heat transfer
60J20 Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.)

Software:

ARPACK
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] P. Deuflhard, M. Dellnitz, O. Junge, Ch. Schütte, Computation of essential molecular dynamics by subdivision techniques, in: P. Deuflhard, J. Hermans, B. Leimkuhler, A.E. Mark, S. Reich, R.D. Skeel (Eds.), 1999, pp. 98-115; P. Deuflhard, M. Dellnitz, O. Junge, Ch. Schütte, Computation of essential molecular dynamics by subdivision techniques, in: P. Deuflhard, J. Hermans, B. Leimkuhler, A.E. Mark, S. Reich, R.D. Skeel (Eds.), 1999, pp. 98-115 · Zbl 0966.81067
[2] Ch. Schütte, A. Fischer, W. Huisinga, P. Deuflhard, A direct approach to conformational dynamics based on hybrid Monte Carlo, J. Comput. Phys. (Special issue on Comput. Biophys.) 151 (1999) 146-168; Ch. Schütte, A. Fischer, W. Huisinga, P. Deuflhard, A direct approach to conformational dynamics based on hybrid Monte Carlo, J. Comput. Phys. (Special issue on Comput. Biophys.) 151 (1999) 146-168 · Zbl 0933.65145
[3] E. Seneta, Nonnegative Matrices and Markov Chains, Series in Statistics, second ed., Springer, Berlin, 1981; E. Seneta, Nonnegative Matrices and Markov Chains, Series in Statistics, second ed., Springer, Berlin, 1981
[4] A. Berman, R.J. Plemmons, Nonnegative Matrices in the Mathematical Sciences, Academic Press, New York, 1979 (reprinted by SIAM, Philadelphia, 1994); A. Berman, R.J. Plemmons, Nonnegative Matrices in the Mathematical Sciences, Academic Press, New York, 1979 (reprinted by SIAM, Philadelphia, 1994) · Zbl 0484.15016
[5] George S. Fishman. Monte Carlo - Concepts, Algorithms, and Applications, Series in Operations Research, Springer, Berlin, 1995; George S. Fishman. Monte Carlo - Concepts, Algorithms, and Applications, Series in Operations Research, Springer, Berlin, 1995 · Zbl 0859.65001
[6] T. Friese, P. Deuflhard, F. Schmidt, A multigrid method for the complex Helmholtz eigenvalue problem, in: C.-H. Lai, P. E. Bjoerstad, M. Cross, O.B. Widlund (Eds.), Domain Decomposition Methods in Sciences and Engineering, DDM-org, New York, 1999, pp. 18-26; T. Friese, P. Deuflhard, F. Schmidt, A multigrid method for the complex Helmholtz eigenvalue problem, in: C.-H. Lai, P. E. Bjoerstad, M. Cross, O.B. Widlund (Eds.), Domain Decomposition Methods in Sciences and Engineering, DDM-org, New York, 1999, pp. 18-26
[7] Meyer, C. D., Stochastic complementation uncoupling Markov chains and the theory of nearly reducible systems, SIAM Rev., 31, 240-272 (1989) · Zbl 0685.65129
[8] G.W. Stewart, On the structure of nearly uncoupled Markov chains, in: G. Iazeolla, P.J. Courtois, A. Hordijk (Eds.), Mathematical Computer Performance and Reliability, Elsevier, New York, 1984, pp. 287-302; G.W. Stewart, On the structure of nearly uncoupled Markov chains, in: G. Iazeolla, P.J. Courtois, A. Hordijk (Eds.), Mathematical Computer Performance and Reliability, Elsevier, New York, 1984, pp. 287-302
[9] T. Kato, Perturbation Theory for Linear Operators, Springer, Berlin, 1995; T. Kato, Perturbation Theory for Linear Operators, Springer, Berlin, 1995 · Zbl 0836.47009
[10] D.J. Hartfiel, C.D. Meyer, On the structure of stochastic matrices with a subdominant eigenvalue near 1. Linear Algebra Appl. 272 (1998) 193-203; D.J. Hartfiel, C.D. Meyer, On the structure of stochastic matrices with a subdominant eigenvalue near 1. Linear Algebra Appl. 272 (1998) 193-203 · Zbl 0892.15017
[11] A. Sinclair, Algorithms for Random Generation and Counting - A Markov Chain Approach, Progress in Theoretical Computer Science, Birkhäuser, Basel, 1993; A. Sinclair, Algorithms for Random Generation and Counting - A Markov Chain Approach, Progress in Theoretical Computer Science, Birkhäuser, Basel, 1993 · Zbl 0780.68096
[12] Lehoucq, R. B.; Sorensen, D. C.; Yang, C., ARPACK User’s Guide: Solution of Large Eigenvalue Problems by Implicit Restartet Arnoldi Methods (1998), Rice University: Rice University Houston · Zbl 0901.65021
[13] D.B. West, Introduction to Graph Theory, Addison-Wesley, Reading, MA, 1996; D.B. West, Introduction to Graph Theory, Addison-Wesley, Reading, MA, 1996 · Zbl 0845.05001
[14] W. Huisinga, C. Best, R. Roitzsch, C. Schütte, F. Cordes, From simulation data to conformational ensembles: structure and dynamic based methods, J. Comp. Chem 20 (16) (1999) 1760-1774; W. Huisinga, C. Best, R. Roitzsch, C. Schütte, F. Cordes, From simulation data to conformational ensembles: structure and dynamic based methods, J. Comp. Chem 20 (16) (1999) 1760-1774
[15] Ryckaert, J.-P.; Bellemans, A., Molecular dynamics of liquid \(n\)-butane near its boiling point, Chem. Phys. Lett., 30, 1, 123-125 (1975)
[16] P. Deuflhard, J. Hermans, B. Leimkuhler, A.E. Mark, S. Reich, R.D. Skeel (Eds.), Computational Molecular Dynamics: Challenges, Methods, Ideas, Lecture Notes in Computational Science and Engineering, vol. 4, Springer, Berlin, 1999; P. Deuflhard, J. Hermans, B. Leimkuhler, A.E. Mark, S. Reich, R.D. Skeel (Eds.), Computational Molecular Dynamics: Challenges, Methods, Ideas, Lecture Notes in Computational Science and Engineering, vol. 4, Springer, Berlin, 1999
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.