
Accession Number : ADA185275
Title : Costs of Quadtree Representation of Nondense Matrices.
Descriptive Note : Technical rept. Sep 84Aug 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 nondense, unpatterned matrices. Those results are exact values for the shuffle and bitreversal 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