Subject: Re: [ublas] Question/request for matrix powers and other stuff
From: Daryle Walker (darylew_at_[hidden])
Date: 2008-10-22 15:38:49
On Oct 22, 2008, at 4:02 AM, Jens Seidel wrote:
> On Tue, Oct 21, 2008 at 04:18:52PM -0400, Daryle Walker wrote:
[SNIP]
>> The code I'm adapting sometimes enters a LOT of zero-values in a row.
>> The original author realized that, since inserting a zero can be
>> expressed as a linear transformation, using the matrix form and
>> raising
>
> Heh?
Let's consider an unsigned integer as a vector of bits. So an octet-
sized byte, i.e. unsigned char, can be expressed like:
L ::= [L0 L1 ... L6 L7]
A CRC step is accomplished whenever a new bit N is inserted by
combining with a given constant G:
[L0 ... L7], N -> [N L0 ... L6] - L7 * [G0 ... G7]
where "-" is XOR and "*" is AND. Whenever N is zero, we can
represent the change as a linear transformation, i.e. matrices! (You
can always force a zero by making all coefficients zero.)
NewL0 = N - L7 * G0 = -L7 * G0 (since N is 0 here)
NewL1 = L0 - L7 * G1
NewL2 = L1 - L7 * G2
...
NewL7 = L6 - L7 * G7
or in row-vector * matrix form:
[0 1 0 ... 0 ]
[0 0 1 ... 0 ]
[NewL0 ... NewL7] = [L0 ... L7] * ...
[0 0 0 ... 1 ]
[G0 G1 G2 ... G7]
(I removed the minus signs because negation is a no-op in GF(2), so
both plus and minus are XOR.) We can code the 8-bit bit vector as an
unsigned char and the matrix as an array of eight unsigned chars. Or
we can also use bool or a custom GF(2) type as an element type and
use the current uBLAS types for the matrices. The original author
used the bit-vector method; while, right now, I'm using the full
object method.
>> it to a power can _save_ time over inserting each zero manually.
>> (The
>> original author used a bit-packing scheme for the GF(2) matrices
>> involved, which I'll add later.) The manual method is by definition
>> linear on the number of zeros added. Using matrices and powers,
>> especially with square-and-multiply, should represent a savings
>> when the
>> length gets long enough.
>
> I don't understand this :-)
You do know that a matrix multiplication can be used to carry out a
linear transformation, right? Multiple transformations in a row can
be compacted by multiplying the corresponding matrices together
before combining with the input vector. Therefore, repeating the
same transformation can be represented by raising the original l.t.
matrix (which has to be square) to the power of the repetitions desired.
You have heard of the square-and-multiply, or binary exponentiation,
method of carrying out an integer power, right? You expand an
exponent to its binary representation, and use that for the
directions to the multiplication order to create the result. (The
value's type has to be associative for multiplication, of course.)
If you have a negative power, turn the value to its multiplicative
inverse (if any) then proceed with the absolute value of the
exponent. A zero power maps to the value's type's multiplicative
identity.
Now, if I'm entering a single zero/false bit value, then doing the
job manually will be faster than setting up a l.t. matrix and using
it. The manual procedure is, by definition, linear on the number of
zeros entered. If the matrix method is used with square-and-
multiply, there will be a count value N where the matrix setup and
usage will be faster than N manual calls (thousands or millions).
That's the point of doing this.
-- Daryle Walker Mac, Internet, and Video Game Junkie darylew AT hotmail DOT com