Browse Prior Art Database

Fast Matrix Vector Products using an Associative Memory

IP.com Disclosure Number: IPCOM000109327D
Original Publication Date: 1992-Aug-01
Included in the Prior Art Database: 2005-Mar-23
Document File: 4 page(s) / 78K

Publishing Venue

IBM

Related People

Miranker, WL: AUTHOR

Abstract

Disclosed is a fast and accurate matrix-vector product device using an associative memory. An application produces an O(1) discrete Fourier transform. Let y = Mx be an exact matrix vector product, and let (Image Omitted) be an approximate product. Let e1 = y - y1 = M(x - M-1 y1).

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 69% of the total text.

Fast Matrix Vector Products using an Associative Memory

       Disclosed is a fast and accurate matrix-vector product
device using an associative memory.  An application produces an O(1)
discrete Fourier transform.
Let
y = Mx
be an exact matrix vector product, and let

                            (Image Omitted)

be an approximate product.  Let
e1 = y - y1
= M(x - M-1 y1).

      Compute a correction using the approximate product, viz
and update y1:
y2 = y1 + c1 .

      At the n th stage we have an approximation yn to y
yn = yn-1 + cn-1,
and we compute
en = M(x - M-1 yn).

      Define
and
yn+1 = yn + cn .

      Now suppose
where
Here p is some positive constant.  Now
assuming is linear.  Then

      Then
where x(M) is the condition number of M.  Thus, the condition
p(1 + p(1 + p)x(M)] & r < 1
assures the convergence of the process.  In particular,

      The operation y = Mx may be (approximately) implemented using
an associative memory.  In particular, let (xi, yi), i = 1, ... , k
be pairs of N-vectors.  Let
X = (x1, ... , xk)
Y = (y1, ... , yk)
be the N x k matrices composed of the indicated columns. Let
M = YX+
where X+ is the pseudoinverse of X.  X+ always exists, but,
X+ = XT(XXT)-1,
in particular, when the latter expression exists.

      Load the associative memory with the (xi, yi) i = 1, ... , k
as (signal, key) pairs.  Then accessing the memory with a vector x
produces output y, where
y = Mx.
(...