NDLI: Updating $LU$ Factorizations for Computing Stationary Distributions

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Plemmons, R. J. Funderlic, R. E.
Copyright Year	1986
Abstract	The computation of stationary probability distributions for Markov chains is important in the analysis of many models in the mathematical sciences, such as queueing network models, input-output economic models and compartmental tracer analysis models. These computations often involve the solution of large-scale homogeneous linear equations by Gaussian elimination, where A is a Q-matrix, i.e., $A = ( a_{ij} )$ is irreducible, $a_{ij} \leqq 0$ for all $i \ne j$ and has zero column sums. The stationary distributions are the components of the unique solution vector x of positive components whose sum is one. Stable direct methods for computing x by triangular factorization $A = LU$ have received considerable attention recently and the purpose of this paper is to provide a stable method for updating the factors L and U in $O( n^2 )$ flops in the case where a column of A is modified. Updating formulas are derived here using an approach similar to that for updating the Cholesky factor of a symmetric positive definite matrix after the addition of a rank one matrix. The algorithm is effective more generally for any matrix that has a stable $LU$ factorization and for which the updated matrix has a stable $LU$ factorization. An error analysis for thw $LU$ update algorithm is outlined along the lines of that given for the Cholesky update by Fletcher and Powell. Details of the algorithm based on the error analysis and other considerations are given.
Starting Page	30
Ending Page	42
Page Count	13
File Format	PDF
ISSN	01965212
DOI	10.1137/0607004
Journal	SIAM Journal on Algebraic Discrete Methods (SJAMDU)
Issue Number	1
Volume Number	7
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2006-07-17
Access Restriction	Subscribed
Subject Keyword	Applications of Markov chains and discrete-time Markov processes on general state spaces Factorization of matrices Direct methods for linear systems and matrix inversion
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in