File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Circulant preconditioners for stochastic automata networks

TitleCirculant preconditioners for stochastic automata networks
Authors
Issue Date2000
PublisherSpringer Verlag. The Journal's web site is located at http://link.springer.de/link/service/journals/00211/index.htm
Citation
Numerische Mathematik, 2000, v. 87 n. 1, p. 35-57 How to Cite?
AbstractStochastic Automata Networks (SANs) are widely used in modeling communication systems, manufacturing systems and computer systems. The SAN approach gives a more compact and efficient representation of the network when compared to the stochastic Petri nets approach. To find the steady state distribution of SANs, it requires solutions of linear systems involving the generator matrices of the SANs. Very often, direct methods such as the LU decomposition are inefficient because of the huge size of the generator matrices. An efficient algorithm should make use of the structure of the matrices. Iterative methods such as the conjugate gradient methods are possible choices. However, their convergence rates are slow in general and preconditioning is required. We note that the MILU and MINV based preconditioners are not appropriate because of their expensive construction cost. In this paper, we consider preconditioners obtained by circulant approximations of SANs. They have low construction cost and can be inverted efficiently. We prove that if only one of the automata is large in size compared to the others, then the preconditioned system of the normal equations will converge very fast. Numerical results for three different SANs solved by CGS are given to illustrate the fast convergence of our method.
Persistent Identifierhttp://hdl.handle.net/10722/75198
ISSN
2023 Impact Factor: 2.1
2023 SCImago Journal Rankings: 1.855
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorChan, RHen_HK
dc.contributor.authorChing, WKen_HK
dc.date.accessioned2010-09-06T07:08:52Z-
dc.date.available2010-09-06T07:08:52Z-
dc.date.issued2000en_HK
dc.identifier.citationNumerische Mathematik, 2000, v. 87 n. 1, p. 35-57en_HK
dc.identifier.issn0029-599Xen_HK
dc.identifier.urihttp://hdl.handle.net/10722/75198-
dc.description.abstractStochastic Automata Networks (SANs) are widely used in modeling communication systems, manufacturing systems and computer systems. The SAN approach gives a more compact and efficient representation of the network when compared to the stochastic Petri nets approach. To find the steady state distribution of SANs, it requires solutions of linear systems involving the generator matrices of the SANs. Very often, direct methods such as the LU decomposition are inefficient because of the huge size of the generator matrices. An efficient algorithm should make use of the structure of the matrices. Iterative methods such as the conjugate gradient methods are possible choices. However, their convergence rates are slow in general and preconditioning is required. We note that the MILU and MINV based preconditioners are not appropriate because of their expensive construction cost. In this paper, we consider preconditioners obtained by circulant approximations of SANs. They have low construction cost and can be inverted efficiently. We prove that if only one of the automata is large in size compared to the others, then the preconditioned system of the normal equations will converge very fast. Numerical results for three different SANs solved by CGS are given to illustrate the fast convergence of our method.en_HK
dc.languageengen_HK
dc.publisherSpringer Verlag. The Journal's web site is located at http://link.springer.de/link/service/journals/00211/index.htmen_HK
dc.relation.ispartofNumerische Mathematiken_HK
dc.titleCirculant preconditioners for stochastic automata networksen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0029-599X&volume=87&spage=35&epage=57&date=2000&atitle=Circulant+Preconditioners+for+Stochastic+Automata+Networksen_HK
dc.identifier.emailChing, WK:wching@hku.hken_HK
dc.identifier.authorityChing, WK=rp00679en_HK
dc.description.naturepostprint-
dc.identifier.doi10.1007/s002110000173-
dc.identifier.scopuseid_2-s2.0-0034555669en_HK
dc.identifier.hkuros63212en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0034555669&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume87en_HK
dc.identifier.issue1en_HK
dc.identifier.spage35en_HK
dc.identifier.epage57en_HK
dc.identifier.isiWOS:000165618300002-
dc.publisher.placeGermanyen_HK
dc.identifier.scopusauthoridChan, RH=7403110910en_HK
dc.identifier.scopusauthoridChing, WK=13310265500en_HK
dc.identifier.issnl0029-599X-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats