Uniform Boundedness of a Preconditioned Normal Matrix Used in Interior-Point Methods

Autor:	Renato D. C. Monteiro, Takashi Tsuchiya, Jerome W. O'Neal
Rok vydání:	2004
Předmět:	Combinatorics Matrix (mathematics) Diagonal matrix MathematicsofComputing_NUMERICALANALYSIS Uniform boundedness Matrix analysis System of linear equations Normal matrix Software Matrix similarity Matrix multiplication Theoretical Computer Science Mathematics
Zdroj:	SIAM Journal on Optimization. 15:96-100
ISSN:	1095-7189 1052-6234
DOI:	10.1137/s1052623403426398
Popis:	Solving systems of linear equations with "normal" matrices of the form A D2 AT is a key ingredient in the computation of search directions for interior-point algorithms. In this article, we establish that a well-known basis preconditioner for such systems of linear equations produces scaled matrices with uniformly bounded condition numbers as D varies over the set of all positive diagonal matrices. In particular, we show that when A is the node--arc incidence matrix of a connected directed graph with one of its rows deleted, then the condition number of the corresponding preconditioned normal matrix is bounded above by m(n - m + 1), where m and n are the number of nodes and arcs of the network.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::3b9ee420da05af3bed20a6743c073820 https://doi.org/10.1137/s1052623403426398 Zobrazit plný text záznamu Plný text ve formátu PDF