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

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)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1987
Accession Number
ADA185781

Entities

People

  • Marcio De Carvalho

Organizations

  • University of California, Berkeley

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algebra
  • Algorithms
  • Arithmetic
  • California
  • Computations
  • Computer Programming
  • Computer Programs
  • Electronic Mail
  • Engineering
  • Heuristic Methods
  • Industrial Engineering
  • Linear Algebra
  • Linear Programming
  • Operations Research
  • Systems Engineering
  • Universities

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.
  • Operations Research