Costs of Quadtree Representation of Non-dense Matrices.

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)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 1987
Accession Number
ADA185275

Entities

People

  • David S. Wise
  • John Franco

Organizations

  • Indiana University Bloomington

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Addressing
  • Air Force
  • Computer Programming
  • Computer Science
  • Computers
  • Decomposition
  • Identities
  • Linear Systems
  • Notation
  • Observation
  • Parallel Computing
  • Parallel Processing
  • Parallel Processors
  • Probability
  • Sparse Matrix
  • Terminals
  • Trees (Data Structures)

Readers

  • Computer Vision.
  • Linear Algebra
  • Parallel and Distributed Computing.