Re: [ublas] Question/request for matrix powers and other stuff

Subject: Re: [ublas] Question/request for matrix powers and other stuff
From: Sebastian Gesemann (s.gesemann_at_[hidden])
Date: 2008-09-26 10:22:41

On Fri, Sep 26, 2008 at 9:22 AM, Daryle Walker <darylew_at_[hidden]> wrote:
> 1.      I looked around at the Boost uBLAS documentation for this but I
> couldn't find it.  Is there a "pow" function or similar that can return a
> given integer power of a square matrix?  (It could use binary exponentiation
> to do its work.

You probably mean "square-and-multiply".

> 2. Is there a matrix type with Boolean elements?  I worked around that
> my making my own GF(2) representation type and using it with the uBLAS class
> templates.  Is using a type that doesn't represent real or complex numbers
> supported?

Sure.

> I originally tried to develop my own
> compact-bit vector and matrix class templates, but thought it was too much
> to test it and my main code, so I made a [non-compact] GF(2) class and
> wrapped uBLAS around that.)

A special bit matrix/vector class can not only be more efficient in
terms of storage space but also be very fast. Similar to how MMX/SSE
allows you to speed up calculations on int- and float vectors, simple
32 bit ints can be used to parallelize your GF(2) calculations. The
binary AND (&) becomes an element-wise product, the binary XOR (^)
becomes an element-wise sum. Summing the bits in a 32-dimensional
vector = computing parity. Here's an (untested!) example:

uint32 parity(uint32 x)
{
   x ^= x >> 16; x ^= x >> 8; x ^= x >> 4; x ^= x >> 2; x ^= x >> 1;
   return x & 1;
}

// scalar product of two vectors over GF(2) given as compressed array
of 32-bit uints (msb-to-lsb order)
uint32 scalar_product_32(size_t dim, const uint32 * a, const uint32 * b)
{
   uint32 acc = 0;
   while (dim >= 32) {
      acc ^= parity(*a & *b);
      ++a; ++b;
      dim -= 32;
   }
   if (dim>0) {  // 0 < dim < 32
      acc ^= parity((*a & *b) & (uint32(-1) << (32-dim)));
   }
   return acc;
}

etc etc etc

Cheers,
SG