Accession Number : ADA185781

Title :   On the Work Needed to Factor a Symmetric Positive Definite Matrix.

Descriptive Note : Technical rept.,

Corporate Author : CALIFORNIA UNIV BERKELEY DEPT OF INDUSTRIAL ENGINEERING AND OPERATIONS RESEA RCH

Personal Author(s) : Carvalho, Marcio de

PDF Url : ADA185781

Report Date : Jun 1987

Pagination or Media Count : 25

Abstract : When comparing different row ordering strategies, the measure often used is the fill-in, or the number of additional non-zeroes elements. This report proposes an another measure: the number of arithmetic operations necessary to factor the matrix. Two classical ordering strategies: Minimum Degree and Minimum Local Fill-in are compared with respect to this measure and Minimum Local Fill-in usually produces better results than Minimum Degree. Also, an application is presented where the number of arithmetic operations may be more interesting measure of performance is presented: Karmarkar's Linear Programming Algorithm. Keywords: Heuristic methods; Numerical linear algebra; Matrix computations; Graph theory. (Author)

Descriptors :   *HEURISTIC METHODS, *FACTOR ANALYSIS, *MATRICES(MATHEMATICS), ALGORITHMS, ARITHMETIC, GRAPHS, LINEAR ALGEBRA, LINEAR PROGRAMMING, NUMERICAL ANALYSIS, THEORY, SYMMETRY, STATISTICAL DATA, PERMUTATIONS

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE