Tech Report CS-00-02

Linear Algebra in Very High-Dimension Vector Spaces: Algorithms and Data Structures for Implementing Exact and Approximate Solution Methods

Kee-Eung Kim, Thomas Dean and Samuel E. Hazlehurst

March 2000

Abstract:

In this paper, we show how certain problems can be recast in terms of equations involving matrices and vectors that are represented implicitly. These matrices and vectors have large explicit representations in the sense that it is practically impossible to even enumerate their indices. Instead, the indices are expressed using a set of index variables that describe the distinguishing features of the problem domain. The matrices and vectors are represented in factored form using compact, easily computed functions of the index variables. The entries of these matrices and vectors are reconstituted on an as-needed basis, often in such a way that computations can be performed on large sets of indices with no more effort than that required for a single index and its corresponding entry. We show how elementary vector and matrix operations can be performed on these implicitly represented matrices and vectors (e.g., scalar and dot products, raising a matrix to a power) and how these basic operations can then be combined to perform more complex calculations (e.g., solving a system of equations). Our motivating examples involve solving Markov decision processes and planning under uncertainty, but the methods described in this paper apply to a wide range of problems.

(complete text in pdf or gzipped postscript)