Re: how to parse linear equations

[Michael Chen]

My goal is to get to the matrix form Ax =b by collecting and combining
linear terms while I am parsing the ast tree. Once I get a clean
matrix form Ax=b, it is straightforward to call my other routines to
solve it.

 I also realized that  symbolic programming or CLP probably need to so
similar things. But no idea what are the algorithms they used.

Michael

On Sat, Jan 16, 2010 at 4:23 AM, Hans Aberg <address@hidden> wrote:
> On 16 Jan 2010, at 01:40, Michael Chen wrote:
>
>> The input I have is linear equation like:
>>
>> 2 * x + ( x - y ) = x + 1
>>
>> And I would like to get at end
>>
>> 2 * x - y = 1
>>
>> I studied the calculator example, and be able to build ast tree.
>> however  I have no way to reduce it. Please give me an example or
>> link. Thanks.
>
> You need methods used in symbolic programming (like Maple), theorem provers,
> and CLP like:
>  http://en.wikipedia.org/wiki/CLP(R)
>  http://en.wikipedia.org/wiki/Constraint_logic_programming
>
> One can solve polynomial equations using Buchberger's Groebner Basis
> Algorithm. Given an ideal (p_1, ..., p_k) it produces a new set of
> generators relative a monomial order on diagonalized form. In the case of
> one variable, it reduces to the Euclidean algorithm computing the greatest
> common denominator. For a set of equations, just write them as p_1 = 0, ...,
> p_k = 0, and apply it to the ideal (p_1, ..., p_k).
>
> If you want to just solve linear equations, you can use just the ordinary
> matrix solution method: write matrices A X = B, and solve it. - Check for
> computationally efficient methods doing this.
>
> When doing it the CLP way, one integrates this algorithm into the
> unification process that i Prolog is used to unify the heads of the clauses.
> This produces a very elegant way to solve them, as you can see on that link
> above, but is somewhat limited if one wants to do more general things.
>
>  Hans
>
>
>



-- 
Best regards,
Michael Chen
Google Voice Phone.: 847-448-0647