0
$\begingroup$

The real world version:

I have a united value (e.i. 12in, 120V 1.414 kg*m/s) where the units are specified as the rational exponents of the 5 base units; m, s, kg, C and K. Additionally, I have a set of non-base units and I want to find the "simplest" combination of those units that matches my value.

The abstract version:

With a little manipulation this can be converted to a very under defined linear combination problem. With a little more work it can be restricted to integer solutions, making it (I think) a linear programming problem (a subject I know almost nothing about).

The part I actualy care about:

What additional constraints/criteria can be applied to this problem to make it solvable and what are the implications of the options? Specifically, I'm looking for a solution that is well documented, simple to evaluate and produces approximately the same results as people would expect.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

You have a collection of elements $u_1, ... u_k$ of $\mathbb{Z}^n$ and you want to see if a particular other vector $v \in \mathbb{Z}^n$ is in their $\mathbb{Z}$-span and, if so, what is the "simplest" linear combination that gets you $v$. Is that correct?

If so, it seems like all you need to do is adapt the pseudoinverse method of finding the least-squares solution to an undetermined system $Ax = v$. The point here is that linear algebra over $\mathbb{Z}$ works almost the same as over a field because $\mathbb{Z}$ is a PID. In particular, row operations behave more or less the way you expect them to, although you have to take care not to divide by an integer. If you don't care about fractional exponents, you might as well compute the pseudoinverse over $\mathbb{Q}$.

(By the way, this is not a linear programming problem because you aren't imposing any constraints that take the form of inequalities.)

Improve this answer
$\endgroup$
6
  • $\begingroup$ Your description is correct (if I'm remembering the terminology correctly) As to it being linear programming, I expect that any usable definition of "simplest" will use inequalities (smallest subset of u), but I'll grant that it might no be in the normal place. $\endgroup$
    – BCS
    Commented Dec 21, 2009 at 22:20
  • $\begingroup$ In a linear program, you want to maximize some linear function subject to some linear inequalities. Here there are no linear inequalities (we're just working with the set of x such that Ax = v), so once you write down what the set of all x looks like, you just want to find the one closest to the origin (presumably), and this is just an issue of projection. No linear programming necessary. $\endgroup$
    – Qiaochu Yuan
    Commented Dec 22, 2009 at 0:03
  • $\begingroup$ Then maybe I should look up what linear programming to clear up my confusion. BTW, is there a know solution the the "find the closest one the the origin" bit. I could probably come up with hack of a solution to it but as far as know solutions go, I'm at a loss as to what to start looking up. $\endgroup$
    – BCS
    Commented Dec 22, 2009 at 1:11
  • $\begingroup$ Yes; it's exactly what I just described. $\endgroup$
    – Qiaochu Yuan
    Commented Dec 22, 2009 at 1:20
  • $\begingroup$ Well maybe I'm ignorant but, first of all, I don't know of an efficient way to find the set of x. Second, if I'm not mistaken, it's a infinite set. I guess I should have said; "are there any know efficient solutions to the problem?" The best I can come up with off hand would be to start enumerating all sub sets of size 1, 2, 3 etc. and checking for solutions in each one. (IIRC O(n!)) $\endgroup$
    – BCS
    Commented Dec 23, 2009 at 1:51
0
$\begingroup$

You could cast it as a constrained optimization problem where the constrains specify that the 5 exponents should match (linear) and the quantity to be minimized is the number of non-zero exponents of the non-base units. This should be tractable for your problem sizes.

However, since you are asking for a simple solution, why not try all possible combinations? I.e. first try all combinations of two non-base units, then three etc. I don't know how many non-base units you have, but I suspect the number is small enough.

Edit: One thing you could try is to minimize the L1-norm of $x$ under the constraint $Ax=b$. That will hopefully give you a sparse solution.

Improve this answer
$\endgroup$
1
  • $\begingroup$ The full set I've got so far is here: dsource.org/projects/scrapple/browser/trunk/units/si.d Categorically, I have 24 type of units so that is the practical upper limit for now. But I'd be surprised if there weren't more that got added later. $\endgroup$
    – BCS
    Commented Dec 23, 2009 at 1:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .