Equation Solvers Using SPAD

FriCAS has various equation solvers, these are usually provided by a 'solve' function.

As far as I can see, each 'solve' function is written specifically for a given type of equation without much common infrastructure or standardisation. I don't think these solvers use rules discussed here.

I would like a solver for say quaternions. It would be good if it could be done in as general way as possible, although given that quaternions are the only noncommutative, associative division algebra there is probably not much scope for generalisation in this case. However, as a general principle it might provide more generality if solvers could be written in terms of axioms and identities.

Waldek has given some information which may help to get started from this thread:

> ** [feature-requests:#10] Add Ability to Write Equation
Solvers for a given Domain.**
>
> FriCAS has quite good support for say, systems of polynomial equations
in field or OrderedRing, see numsolve.spad.pamphlet for more details.
>
> Would it be possible to generalise this so that someone writing code for
an SPAD domain can add their own equation solvers for their domain.
With variables that represent elements of that domain.
>
> So, for example, we might want to write equations where the variables
are quaternions. So we need to write a solver which can handle a
non-commuting algebra.
>
> I suppose someone could write some code in SPAD to do
this now? But it really needs a proper framework to do it efficiently?
>

You can write solvers just now.  Existing solvers are packages
which export 'solve' function.  Of course, you need an algorithm
for given domain.  Given system of linear equations over quaternions
one can convert it to a bigger linear system over base ring
and call existing solver.  Then convert back to quaternions.
In principle similar approach may work for polynomial equations,
but even simple polynomial equations over quaternions will
produce complicated equations over base ring.  Directly working
with quaternions may produce better solver.

Anyway, the main problems is to find a method of solving for
given domain.


-- 
                              Waldek Hebisch 

and:

> > You can write solvers just now.  Existing solvers are packages
> > which export 'solve' function.  Of course, you need an algorithm
> > for given domain.  Given system of linear equations over quaternions
> > one can convert it to a bigger linear system over base ring
> > and call existing solver.  Then convert back to quaternions.
> > In principle similar approach may work for polynomial equations,
> > but even simple polynomial equations over quaternions will
> > produce complicated equations over base ring.  Directly working
> > with quaternions may produce better solver.
> >
> > Anyway, the main problems is to find a method of solving for
> > given domain.
>
> OK thanks, I did not know this, it looks useful I'll have to experiment
> with it. Do you know of any tutorials?

Basically, for the interpreter 'solve' is just like another function.
If you add a new one normal overloading resolution will choose
appropriate one.  You need some way of writing equations.
If you want to have '=' sign, then you can use Equation domain.
Eqation can do only a little: '=' sign on command line will
create equation, you can extract left hand side and right
hand side.  

For both sides you need some representation of terms.  For
polynomial Polynomial is good choice, but for noncommutative
domains you need someting different.  We have 'XPolynomial'
domain which may work OK.  I write 'may work' because
'XPolynomial' assumes that variables commute with coefficients
which strictly speaking is not true if you work with equations
over noncommutative ring.  This is OK if you take coefficients
from the base ring.  And any system of algebraic equations can
be written is such a way that you never multiply variable by
noncommuting coefficient.  The problem is that if you are
not careful writing your equation, then 'XPolynomial' will
change relative order of coefficients and variables which
may lead to inequivalent system.  So, it may be wise to
create a generalization of 'XPolynomial' which preserves
relative order of variables and coefficients.

Anyway, if you have a finite dimensional algebra over a
commutative ring (like Quaternion), then you can
replace each variable from the algebra by a linear
combination of basis elements with coefficients form
base ring.  So, instead of 'x' in quaternion you will
have 'x1 + i*x2 + j*x3 + k*x4'.  Practically, this can
be done by using say 'Quaternion(Polyniomial(Fraction(Integer)))'
and defining appropriate mapping from noncommutative
polynomials (which represent your equations) to the
quaternions with polynomial coefficients.  For polynomials
there is 'PolynomialCategoryLifting' package which
helps building mappings between polynomials and a commitative ring.
Something similar would be needed form noncommutative
polynomials.

Note that the approch above is rather naive and potentially
quite inefficient.

In general case, one can use Expression to represent
equations.  The real difficulty is to have solving
algorithm.  Basically any open problem in mathematics
can be formulated as question about solutions of
aproproate equations, so it unlikely that any general
method exists.

(1) -> )di op solve

There are 33 exposed functions called solve :
   [1] (List(Fraction(Polynomial(Integer))),D3) -> List(List(Equation(
            Polynomial(D3))))
            from FloatingRealPackage(D3) if D3 has Join(OrderedRing,
            Field)
   [2] (List(Equation(Fraction(Polynomial(Integer)))),D3) -> List(List(
            Equation(Polynomial(D3))))
            from FloatingRealPackage(D3) if D3 has Join(OrderedRing,
            Field)
   [3] (Fraction(Polynomial(Integer)),D3) -> List(Equation(Polynomial(
            D3)))
            from FloatingRealPackage(D3) if D3 has Join(OrderedRing,
            Field)
   [4] (Equation(Fraction(Polynomial(Integer))),D3) -> List(Equation(
            Polynomial(D3)))
            from FloatingRealPackage(D3) if D3 has Join(OrderedRing,
            Field)
   [5] (D2,D3,Symbol) -> Union(Record(particular: D3,basis: List(D3)),
            "failed")
            from ElementaryFunctionLODESolver(D5,D3,D2)
            if D5 has Join(Comparable,EuclideanDomain,RetractableTo(
            Integer),LinearlyExplicitRingOver(Integer),
            CharacteristicZero) and D3 has Join(                             
            AlgebraicallyClosedFunctionSpace(D5),                            
            TranscendentalFunctionCategory,PrimitiveFunctionCategory)        
            and D2 has LODOCAT(D3)                                           
   [6] (D2,D1,Symbol,D1,List(D1)) -> Union(D1,"failed")                      
            from ElementaryFunctionLODESolver(D5,D1,D2)                      
            if D1 has Join(AlgebraicallyClosedFunctionSpace(D5),             
            TranscendentalFunctionCategory,PrimitiveFunctionCategory)        
            and D5 has Join(Comparable,EuclideanDomain,RetractableTo(        
            Integer),LinearlyExplicitRingOver(Integer),                      
            CharacteristicZero) and D2 has LODOCAT(D1)                       
   [7] (D2,D3) -> Record(particular: Union(D3,"failed"),basis: List(D3)      
            )                                                                
            from LinearSystemMatrixPackage(D4,D5,D3,D2)                      
            if D4 has FIELD and D5 has Join(FiniteLinearAggregate(D4),       
            shallowlyMutable) and D3 has Join(FiniteLinearAggregate(D4)      
            ,shallowlyMutable) and D2 has MATCAT(D4,D5,D3)                   
   [8] (D2,List(D6)) -> List(Record(particular: Union(D6,"failed"),          
            basis: List(D6)))                                                
            from LinearSystemMatrixPackage(D4,D5,D6,D2)                      
            if D6 has Join(FiniteLinearAggregate(D4),shallowlyMutable)       
            and D4 has FIELD and D5 has Join(FiniteLinearAggregate(D4),      
            shallowlyMutable) and D2 has MATCAT(D4,D5,D6)                    
   [9] (Matrix(D4),Vector(D4)) -> Record(particular: Union(Vector(D4),       
            "failed"),basis: List(Vector(D4)))                               
            from LinearSystemMatrixPackage1(D4) if D4 has FIELD
   [10] (List(List(D4)),Vector(D4)) -> Record(particular: Union(Vector(
            D4),"failed"),basis: List(Vector(D4)))
            from LinearSystemMatrixPackage1(D4) if D4 has FIELD
   [11] (Matrix(D4),List(Vector(D4))) -> List(Record(particular: Union(
            Vector(D4),"failed"),basis: List(Vector(D4))))
            from LinearSystemMatrixPackage1(D4) if D4 has FIELD
   [12] (List(List(D4)),List(Vector(D4))) -> List(Record(particular: 
            Union(Vector(D4),"failed"),basis: List(Vector(D4))))
            from LinearSystemMatrixPackage1(D4) if D4 has FIELD
   [13] (Matrix(D6),Vector(D6),Symbol) -> Union(Record(particular: 
            Vector(D6),basis: List(Vector(D6))),"failed")
            from ElementaryFunctionODESolver(D5,D6)
            if D6 has Join(AlgebraicallyClosedFunctionSpace(D5),
            TranscendentalFunctionCategory,PrimitiveFunctionCategory) 
            and D5 has Join(Comparable,EuclideanDomain,RetractableTo(
            Integer),LinearlyExplicitRingOver(Integer),
            CharacteristicZero)
   [14] (Matrix(D5),Symbol) -> Union(List(Vector(D5)),"failed")
            from ElementaryFunctionODESolver(D4,D5)
            if D5 has Join(AlgebraicallyClosedFunctionSpace(D4),
            TranscendentalFunctionCategory,PrimitiveFunctionCategory) 
            and D4 has Join(Comparable,EuclideanDomain,RetractableTo(
            Integer),LinearlyExplicitRingOver(Integer),
            CharacteristicZero)
   [15] (List(Equation(D6)),List(BasicOperator),Symbol) -> Union(
            Record(particular: Vector(D6),basis: List(Vector(D6))),"failed")
            from ElementaryFunctionODESolver(D5,D6)
            if D6 has Join(AlgebraicallyClosedFunctionSpace(D5),
            TranscendentalFunctionCategory,PrimitiveFunctionCategory) 
            and D5 has Join(Comparable,EuclideanDomain,RetractableTo(
            Integer),LinearlyExplicitRingOver(Integer),
            CharacteristicZero)
   [16] (List(D6),List(BasicOperator),Symbol) -> Union(Record(
            particular: Vector(D6),basis: List(Vector(D6))),"failed")
            from ElementaryFunctionODESolver(D5,D6)
            if D6 has Join(AlgebraicallyClosedFunctionSpace(D5),
            TranscendentalFunctionCategory,PrimitiveFunctionCategory) 
            and D5 has Join(Comparable,EuclideanDomain,RetractableTo(
            Integer),LinearlyExplicitRingOver(Integer),
            CharacteristicZero)
   [17] (Equation(D6),BasicOperator,Symbol) -> Union(Record(particular
            : D6,basis: List(D6)),D6,"failed")
            from ElementaryFunctionODESolver(D5,D6)
            if D6 has Join(AlgebraicallyClosedFunctionSpace(D5),
            TranscendentalFunctionCategory,PrimitiveFunctionCategory) 
            and D5 has Join(Comparable,EuclideanDomain,RetractableTo(
            Integer),LinearlyExplicitRingOver(Integer),
            CharacteristicZero)
   [18] (D2,BasicOperator,Symbol) -> Union(Record(particular: D2,basis
            : List(D2)),D2,"failed")
            from ElementaryFunctionODESolver(D5,D2)
            if D5 has Join(Comparable,EuclideanDomain,RetractableTo(
            Integer),LinearlyExplicitRingOver(Integer),
            CharacteristicZero) and D2 has Join(
            AlgebraicallyClosedFunctionSpace(D5),
            TranscendentalFunctionCategory,PrimitiveFunctionCategory)
         
   [19] (Equation(D1),BasicOperator,Equation(D1),List(D1)) -> Union(D1,
            "failed")
            from ElementaryFunctionODESolver(D5,D1)
            if D1 has Join(AlgebraicallyClosedFunctionSpace(D5),
            TranscendentalFunctionCategory,PrimitiveFunctionCategory) 
            and D5 has Join(Comparable,EuclideanDomain,RetractableTo(
            Integer),LinearlyExplicitRingOver(Integer),
            CharacteristicZero)
   [20] (D1,BasicOperator,Equation(D1),List(D1)) -> Union(D1,"failed")
            from ElementaryFunctionODESolver(D5,D1)
            if D1 has Join(AlgebraicallyClosedFunctionSpace(D5),
            TranscendentalFunctionCategory,PrimitiveFunctionCategory) 
            and D5 has Join(Comparable,EuclideanDomain,RetractableTo(
            Integer),LinearlyExplicitRingOver(Integer),
            CharacteristicZero)
   [21] Expression(D3) -> List(Equation(Expression(D3)))
            from TransSolvePackage(D3)
            if D3 has Join(Comparable,EuclideanDomain,RetractableTo(
            Integer),LinearlyExplicitRingOver(Integer),
            CharacteristicZero)
   [22] Equation(Expression(D3)) -> List(Equation(Expression(D3)))
            from TransSolvePackage(D3)
            if D3 has Join(Comparable,EuclideanDomain,RetractableTo(
            Integer),LinearlyExplicitRingOver(Integer),
            CharacteristicZero)
   [23] (Equation(Expression(D4)),Symbol) -> List(Equation(Expression(
            D4)))
            from TransSolvePackage(D4)
            if D4 has Join(Comparable,EuclideanDomain,RetractableTo(
            Integer),LinearlyExplicitRingOver(Integer),
            CharacteristicZero)
   [24] (Expression(D4),Symbol) -> List(Equation(Expression(D4)))
            from TransSolvePackage(D4)
            if D4 has Join(Comparable,EuclideanDomain,RetractableTo(
            Integer),LinearlyExplicitRingOver(Integer),
            CharacteristicZero)
   [25] (List(Equation(Expression(D4))),List(Symbol)) -> List(List(
            Equation(Expression(D4))))
            from TransSolvePackage(D4)
            if D4 has Join(Comparable,EuclideanDomain,RetractableTo(
            Integer),LinearlyExplicitRingOver(Integer),
            CharacteristicZero)
   [26] (List(Fraction(Polynomial(D4))),List(Symbol)) -> List(List(
            Equation(Fraction(Polynomial(D4)))))
            from SystemSolvePackage(D4) if D4 has INTDOM
   [27] (List(Equation(Fraction(Polynomial(D4)))),List(Symbol)) -> List
            (List(Equation(Fraction(Polynomial(D4)))))
            from SystemSolvePackage(D4) if D4 has INTDOM
   [28] List(Fraction(Polynomial(D3))) -> List(List(Equation(Fraction(
            Polynomial(D3)))))
            from SystemSolvePackage(D3) if D3 has INTDOM
   [29] List(Equation(Fraction(Polynomial(D3)))) -> List(List(Equation(
            Fraction(Polynomial(D3)))))
            from SystemSolvePackage(D3) if D3 has INTDOM
   [30] (Fraction(Polynomial(D4)),Symbol) -> List(Equation(Fraction(
            Polynomial(D4))))
            from SystemSolvePackage(D4) if D4 has INTDOM
   [31] (Equation(Fraction(Polynomial(D4))),Symbol) -> List(Equation(
            Fraction(Polynomial(D4))))
            from SystemSolvePackage(D4) if D4 has INTDOM
   [32] Fraction(Polynomial(D3)) -> List(Equation(Fraction(Polynomial(
            D3))))
            from SystemSolvePackage(D3) if D3 has INTDOM
   [33] Equation(Fraction(Polynomial(D3))) -> List(Equation(Fraction(
            Polynomial(D3))))
            from SystemSolvePackage(D3) if D3 has INTDOM

There are 7 unexposed functions called solve :
   [1] (List(Polynomial(D4)),List(Symbol)) -> List(List(Equation(
            Fraction(Polynomial(D4)))))
            from NonLinearSolvePackage(D4) if D4 has INTDOM
   [2] List(Polynomial(D3)) -> List(List(Equation(Fraction(Polynomial(
            D3)))))
            from NonLinearSolvePackage(D3) if D3 has INTDOM
   [3] (D1,D1,BasicOperator,Symbol) -> Union(D1,"failed")
            from NonLinearFirstOrderODESolver(D4,D1)
            if D4 has Join(Comparable,EuclideanDomain,RetractableTo(
            Integer),LinearlyExplicitRingOver(Integer),
            CharacteristicZero) and D1 has Join(
            AlgebraicallyClosedFunctionSpace(D4),
            TranscendentalFunctionCategory,PrimitiveFunctionCategory)
         
   [4] (Matrix(D5),Vector(D5),((D6,D5) -> Union(Record(particular: D5,
            basis: List(D5)),"failed"))) -> Union(Record(particular: Vector(
            D5),basis: Matrix(D5)),"failed")
            from SystemODESolver(D5,D6)
            if D5 has FIELD and D6 has LODOCAT(D5)
   [5] (Polynomial(Fraction(Integer)),Float) -> List(Float)
            from RealSolvePackage
   [6] (Polynomial(Integer),Float) -> List(Float) from RealSolvePackage
            
   [7] D2 -> List(D3) from PolynomialSolveByFormulas(D2,D3)
            if D3 has Field with 
               ?^? : (%,Fraction(Integer)) -> % and D2 has UPOLYC(
            D3)

 

 


metadata block
see also:
Correspondence about this page

Book Shop - Further reading.

Where I can, I have put links to Amazon for books that are relevant to the subject, click on the appropriate country flag to get more details of the book or to buy it from them.

 

This site may have errors. Don't use for critical systems.

Copyright (c) 1998-2017 Martin John Baker - All rights reserved - privacy policy.