Browse Prior Art Database

FINITE SPARSE MATRIX TECHNIQUES

IP.com Disclosure Number: IPCOM000128162D
Original Publication Date: 1979-Dec-31
Included in the Prior Art Database: 2005-Sep-15

Publishing Venue

Software Patent Institute

Related People

ERWIN H. BAREISS: AUTHOR [+3]

Abstract

A unified theory of finite sparse matrix techniques is presented based on a literature search 'and new results. It is intended to aid in computational work and symbolic manipulation of large sparse systems of linear equations. The theory relies on the bijection property of bipartite graph and rectangular Boolean matrix representation. The concept of perfect elimination matrices is extended from the classification under simi larity transformations to that under equivalence transformations with permutation matrices. The reducibility problem is treated with a new and simpler proof than found in the literature. A number of useful algorithms are described. The minimum deficiency algorithms are extended to the new classifi-cation, where the latter required a different technique of proof.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 6% of the total text.

Page 1 of 69

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

FINITE SPARSE MATRIX TECHNIQUES

ERWIN H. BAREISS Northwestern University and CONSUELO MAULINO de PENIZA Northwestern University and Universidad Central de Venezuela

No. 79-13-NM-04

This report was prepared as an account of work spon-sored by the United States Government. Neither the United States nor the U. S. Department of Energy, nor any of their employees, nor any of their contractors, subcontractors, or their employees, makes any warranty, expressed or implied, or assumes any liability or re-sponsibility for the accuracy, completeness, or use- fulness of any information, apparatus, product or pro-cess disclosed or represents that its use would not infringe privately owned rights.

November '1979

PREPARED FOR THE U.S. DEPARTMENT OF ENERGY UNDER CONTRACT NO. EY-76-S- 02-2280

ABSTRACT

A unified theory of finite sparse matrix techniques is presented based on a literature search 'and new results. It is intended to aid in computational work and symbolic manipulation of large sparse systems of linear equations. The theory relies on the bijection property of bipartite graph and rectangular Boolean matrix representation. The concept of perfect elimination matrices is extended from the classification under simi larity transformations to that under equivalence transformations with permutation matrices. The reducibility problem is treated with a new and simpler proof than found in the literature. A number of useful algorithms are described. The minimum deficiency algorithms are extended to the new classifi-cation, where the latter required a different technique of proof.

TABLE OF CONTENTS

Abstract.

0. Introduction. 1

I. Representation of Matrix Structures by Graphs.

1.1. Definitions and Theorems in Graph Theory.

1.2. Matrices and Graphs. 16

II. Reducibility. 21 2.1. Reduction by Permutation Matrices. 21 2.2. Tarjan's Algorithm. 34

Northwestern University Page 1 Dec 31, 1979

Page 2 of 69

FINITE SPARSE MATRIX TECHNIQUES

III. Solution of Sparse Systems of Linear Equations by Direct Methods. 3.1. Gaussian Elimination and Graph Theory. 43 3.2. Ordering Problems. 53 IV. Storage Schemes. 62 4.1. Non'symmetric Case (Schemes I, II, 111). 62 4.2. Symmetric Case (Schemes IV, V, VIE). 66

V. Algorithms for Solving the Problem Ax = b. 71 5.1. Pivotal ordering algorithms. 72 5.2. Desirable Forms for Gaussian Elimination. 5.3. Nested Dissection Method. 90

INTRODUCTION

The main problem in this paper is directed toward the efficient SO- lution of a linear system of equations, Ax = b, when the matrix is sparse and non-singular, with elements either numbers or symbols, and Gaussian elimination or a related direct method is applied. To unify and extend existing algorithms, we introduce bipartite graphs associated with A and consider the elimination process as vertex elimination. This approach permits the possibility of using orderings of the form P T AQ where A may be square or rectangular.

In Ch...