Browse Prior Art Database

Tree Graph Incidence Matrix Triangulization and Inversion Algorithm

IP.com Disclosure Number: IPCOM000077264D
Original Publication Date: 1972-Jul-01
Included in the Prior Art Database: 2005-Feb-25
Document File: 1 page(s) / 12K

Publishing Venue

IBM

Related People

Kugel, LE: AUTHOR

Abstract

The tree submatrix of a nodal incidence matrix of a topological graph is rapidly triangularized or inverted by this algorithm.

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

Page 1 of 1

Tree Graph Incidence Matrix Triangulization and Inversion Algorithm

The tree submatrix of a nodal incidence matrix of a topological graph is rapidly triangularized or inverted by this algorithm.

The operation of this algorithm uses sparse matrix forms of the incidence matrix and transposed incidence matrix of a tree graph. From this incidence matrix information, every path from the datum node (also called the reference or ground node) to every other node is identified in the least number of computer operations. Each node to datum path is identified by the node number of the end node.

Finding the sequence of datum to node paths such that datum to node path ^ contains a branch (defined as branch ^) not in subsequent datum to node paths, h+1, ^+2, ^+3,...n. This sequence of datum to node paths is the permutation vector, which will rearrange the rows of the incident-matrix such that the incidence matrix is lower triangular. This routine generates that sequence.

Inversion of the datum to node path matrix is accomplished by a very simple relationship. The matrix containing all the datum to node paths as column vectors equals the inverse of the transposed incidence matrix of the tree graph.

The algorithm uses two vector lists to trace the datum to node path. NLIST (^) contains the sequence of nodes in the path. BLIST (^) contains the sequence of branches in the path. The information in NLIST and BLIST completely describe a datum to node path. The algorithm requires that...