Accession Number:

ADA551898

Title:

Algorithms for the Equilibration of Matrices and Their Application to Limited-Memory Quasi-Newton Methods

Descriptive Note:

Doctoral thesis

Corporate Author:

STANFORD UNIV CA

Personal Author(s):

• Bradley, Andrew M.

Report Date:

2010-05-01

Pagination or Media Count:

111.0

Abstract:

Diagonally scaling a matrix often reduces its condition number. Equilibration scales a matrix so that the row and column norms are equal. We review the existence and uniqueness theory for exact equilibration. Then we introduce a formalization of approximate equilibration and develop its existence and uniqueness theory. Next we develop approximate equilibration algorithms that access a matrix only by matrix-vector products. We address both the nonsymmetric and symmetric cases. Limited-memory quasi-Newton methods may be thought of as changing the metric so that the steepest-descent method works effectively on the problem. Quasi-Newton methods construct a matrix using vectors of two types involving the iterates and gradients. The vectors are related by an approximate matrix-vector product. Using our approximate matrix-free symmetric equilibration method, we develop a limited-memory quasi-Newton method in which one part of the quasi-Newton matrix approximately equilibrates the Hessian. Often a differential equation is solved by discretizing it on a sequence of increasingly fine meshes. This technique can be used when solving differential-equation-constrained optimization problems. We describe a method to interpolate our limited-memory quasi-Newton matrix from a coarse to a fine mesh.

Descriptors:

• *ALGORITHMS
• *MEMORY DEVICES
• ACCESS
• ASYMMETRY
• DIFFERENTIAL EQUATIONS
• GRADIENTS
• MESH
• OPTIMIZATION
• SCALING FACTOR
• SEQUENCES
• SYMMETRY
• THEORY

Subject Categories:

• Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE