Accession Number : ADA185275

Title :   Costs of Quadtree Representation of Non-dense Matrices.

Descriptive Note : Technical rept. Sep 84-Aug 87,

Corporate Author : INDIANA UNIV AT BLOOMINGTON DEPT OF COMPUTER SCIENCE

Personal Author(s) : Wise, David S ; Franco, John

PDF Url : ADA185275

Report Date : Aug 1987

Pagination or Media Count : 28

Abstract : Quadtree representation of matrices offers a homogeneous representation for both sparse and dense matrices, with advantages for processing on multiprocessors. This paper offers exact values for the average depth and on the number of nodes in this representation of some familiar patterned matrices: symmetric, triangular, and banded. It similarly measures three permutation matrices as comparative examples of non-dense, unpatterned matrices. Those results are exact values for the shuffle and bit-reversal permutations raised by the fast Fourier transform, as well as tight bounds on the expected values from purely random permutations. Two different measures for density and for sparsity are proposed from these values, and a simple analysis of quadtree matrix addition is given as an illustration of these measures. (Author)

Descriptors :   *SPARSE MATRIX, MULTIPROCESSORS, DENSITY, NODES, LINEAR ALGEBRA, PERMUTATIONS, FAST FOURIER TRANSFORMS, ALGORITHMS, SYMMETRY

Subject Categories : Numerical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE