[<<][staapl][>>][..]
Mon Sep 14 09:52:06 CEST 2009

Linear equations

So... This constraint business.  The current algorithm uses N x 1
constraints.  This needs to be generalized to N x 1 linear
constraints, then N x M systems.

Let's start with the most general first.  I.e. a 3 x 2 system:

  a x + b y + c z = d
  q x + r y + s z = t

In general this can be solved using gaussian elimination[1].  Given a
collection of known variables, a square system can be constructed
which then needs to be inverted.  Since all coefficients are known at
compile time, the sequence of computations can be generated in-line to
produce a dataflow program, which can then be sequenced.

Pivoting[2] can be used to yield optimal condition.  Full-pivoting
searches for the element with largest absolute value in the
unprocessed rows.

OK.. since this is all quite straightforward computable at run-time,
it might be good to do it numericall.  Otoh, allowing rational numbers
might be interesting too (i.e. for sparse systems).

Yes, let's go for the rational numbers.  Wait, since there are going
to be square roots of 2 and 3 in the constants, maybe also use field
extensions?

It looks like it might be a good idea to abstract the _coefficient
domain_ of the equations using some kind of unit interface (like the
functor approach in [3]).


[1] http://en.wikipedia.org/wiki/Gaussian_elimination
[2] http://en.wikipedia.org/wiki/Pivoting
[3] http://www.cas.mcmaster.ca/~carette/publications/scp_metamonads.pdf




[Reply][About]
[<<][staapl][>>][..]