
Ublas : 
Subject: Re: [ublas] Question/request for matrix powers and other stuff
From: Sebastian Gesemann (s.gesemann_at_[hidden])
Date: 20080926 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 "squareandmultiply".
> 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
> compactbit vector and matrix class templates, but thought it was too much
> to test it and my main code, so I made a [noncompact] 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 elementwise product, the binary XOR (^)
becomes an elementwise sum. Summing the bits in a 32dimensional
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 32bit uints (msbtolsb 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) << (32dim)));
}
return acc;
}
etc etc etc
Cheers,
SG