IMPLEMENTATION AND COMPUTATIONAL RESULTS FOR THE HIERARCHICAL ALGORITHM FOR MAKING SPARSE MATRICES SPARSER

Citation
Sf. Chang et St. Mccormick, IMPLEMENTATION AND COMPUTATIONAL RESULTS FOR THE HIERARCHICAL ALGORITHM FOR MAKING SPARSE MATRICES SPARSER, ACM transactions on mathematical software, 19(3), 1993, pp. 419-441
Citations number
17
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Computer Sciences",Mathematics
ISSN journal
0098-3500
Volume
19
Issue
3
Year of publication
1993
Pages
419 - 441
Database
ISI
SICI code
0098-3500(1993)19:3<419:IACRFT>2.0.ZU;2-V
Abstract
If A is the (sparse) coefficient matrix of linear-equality constraints , for what nonsingular T is A = TA as sparse as possible, and how can it be efficiently computed? An efficient algorithm for this Sparsity P roblem (SP) would be a valuable preprocessor for linearly constrained optimization problems. In a companion paper we developed a two-pass ap proach to solve SP called the Hierarchical Algorithm, In this paper we report on how we implemented the Hierarchical Algorithm into a code c alled HASP, and our computational experience in testing HASP on the NE TLIB linear-programming problems. We found that HASP substantially out performed a previous code for SP and that it produced a net savings in optimization time on the NETLIB problems. The results allow us to giv e guidelines for its use in practice.