Costs of Quadtree Representation of Non-dense Matrices.
- 1 August 1987
- report
- Published by Defense Technical Information Center (DTIC)
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)Keywords
This publication has 0 references indexed in Scilit: