ApCoCoA-1:CharP.IMNLASolve

From ApCoCoAWiki
Revision as of 14:08, 14 December 2010 by Stadler (talk | contribs)

CharP.GBasisF2

Computes the unique F_2-rational zero of a given polynomial system over F_2.

Syntax

CharP.IMNLASolve(F:LIST):LIST

Description

Please note: The function(s) explained on this page is/are using the ApCoCoAServer. You will have to start the ApCoCoAServer in order to use it/them.


This function computes the unique zero in F_2^n of a polynomial system over F_2. It uses Improved Mutant NLA-Algorithm to find the unique zero. The Improved Mutant NLA-Algorithm generates a sequence of linear systems to solve the given system. The Improved Mutant NLA-Algorithm can find the unique zero only. If the given polynomial system has more than one zeros in F_2^n then this function does not find any zero. In this case a massage for non-uniqueness will be displayed to the screen after reaching the maximum degree bound. In fact Improved Mutant NLA-Algorithm is the NLA-Algorithm with improved mutant strategy. It uses LinAlg.EF for gaussian elimination.

  • @param F: List of polynomials of given system.

  • @return Possibly the unique solution of the given system in F_2^n.

Example

Use Z/(2)[x[1..4]];
F:=[
    x[1]x[2] + x[2]x[3] + x[2]x[4] + x[3]x[4] + x[1] + x[3] + 1, 
    x[1]x[2] + x[1]x[3] + x[1]x[4] + x[3]x[4] + x[2] + x[3] + 1, 
    x[1]x[2] + x[1]x[3] + x[2]x[3] + x[3]x[4] + x[1] + x[4] + 1, 
    x[1]x[3] + x[2]x[3] + x[1]x[4] + x[2]x[4] + 1
    ];


-- Then we compute the solution with
CharP.IMNLASolve(F);

-- And we achieve the following information on the screen together with the solution at the end.
----------------------------------------
      Finding Variable: x[4]
	The size of Matrix is:
		No. of Rows=4
		No. of Columns=11
Appling Gaussian Elimination for finding Mutants...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Compeleted.
	The size of Matrix is:
		No. of Rows=4
		No. of Columns=11
Appling Gaussian Elimination for finding Mutants...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Compeleted.
	The size of Matrix is:
		No. of Rows=11
		No. of Columns=5
Appling Gaussian Elimination to check solution coordinate...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Completed.
	The size of Matrix is:
		No. of Rows=11
		No. of Columns=5
Appling Gaussian Elimination to check solution coordinate...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Completed.
	No. of New Mutants found = 0
	The size of Matrix is:
		No. of Rows=8
		No. of Columns=11
Appling Gaussian Elimination for finding Mutants...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Compeleted.
	The size of Matrix is:
		No. of Rows=11
		No. of Columns=8
Appling Gaussian Elimination to check solution coordinate...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Completed.
	The size of Matrix is:
		No. of Rows=11
		No. of Columns=8
Appling Gaussian Elimination to check solution coordinate...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Completed.
	No. of New Mutants found = 1
	The total No. of Mutants found are = 1
	The No. of Mutants of Minimum degree (Mutants used) are = 1
	The size of Matrix is:
		No. of Rows=11
		No. of Columns=11
Appling Gaussian Elimination for finding Mutants...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Compeleted.
	The size of Matrix is:
		No. of Rows=11
		No. of Columns=10
Appling Gaussian Elimination to check solution coordinate...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Completed.
	The size of Matrix is:
		No. of Rows=11
		No. of Columns=10
Appling Gaussian Elimination to check solution coordinate...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Completed.
x[4] = 1
 Finding Variable: x[3]
	The size of Matrix is:
		No. of Rows=4
		No. of Columns=7
Appling Gaussian Elimination for finding Mutants...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Compeleted.
	The size of Matrix is:
		No. of Rows=4
		No. of Columns=7
Appling Gaussian Elimination for finding Mutants...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Compeleted.
	The size of Matrix is:
		No. of Rows=7
		No. of Columns=5
Appling Gaussian Elimination to check solution coordinate...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Completed.
	The size of Matrix is:
		No. of Rows=7
		No. of Columns=5
Appling Gaussian Elimination to check solution coordinate...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Completed.
	No. of New Mutants found = 0
	The size of Matrix is:
		No. of Rows=4
		No. of Columns=7
Appling Gaussian Elimination for finding Mutants...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Compeleted.
	The size of Matrix is:
		No. of Rows=7
		No. of Columns=5
Appling Gaussian Elimination to check solution coordinate...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Completed.
	The size of Matrix is:
		No. of Rows=7
		No. of Columns=5
Appling Gaussian Elimination to check solution coordinate...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Completed.
	No. of New Mutants found = 0
	The size of Matrix is:
		No. of Rows=7
		No. of Columns=7
Appling Gaussian Elimination for finding Mutants...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Compeleted.
	The size of Matrix is:
		No. of Rows=7
		No. of Columns=7
Appling Gaussian Elimination to check solution coordinate...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Completed.
x[3] = 0
 Finding Variable: x[2]
	The size of Matrix is:
		No. of Rows=3
		No. of Columns=4
Appling Gaussian Elimination for finding Mutants...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Compeleted.
	The size of Matrix is:
		No. of Rows=3
		No. of Columns=4
Appling Gaussian Elimination for finding Mutants...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Compeleted.
	The size of Matrix is:
		No. of Rows=4
		No. of Columns=4
Appling Gaussian Elimination to check solution coordinate...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Completed.
	The size of Matrix is:
		No. of Rows=4
		No. of Columns=4
Appling Gaussian Elimination to check solution coordinate...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Completed.
x[2] = 1
[0, 1, 0, 1]


Example

Use Z/(2)[x[1..4]];
F:=[ 
    x[2]x[3] + x[1]x[4] + x[2]x[4] + x[3]x[4] + x[1] + x[2] + x[3] + x[4], 
    x[2]x[3] + x[2]x[4] + x[3]x[4] + x[2] + x[3] + x[4],  
    x[1]x[2] + x[2]x[3] + x[2]x[4] + x[3]x[4] + x[1] + x[2],  
    x[1]x[2] + x[2]x[3] + x[2]x[4] + x[3]x[4] + x[1] + x[2]
   ];

-- Solution is not unique i.e. [0, 1, 1, 1], [0, 0, 0, 0], and [1, 1, 1, 1] are solutions 

-- Then we compute the solution with
CharP.IMNLASolve(F);

-- And we achieve the following information on the screen.
----------------------------------------
    Finding Variable: x[4]
	The size of Matrix is:
		No. of Rows=4
		No. of Columns=9
Appling Gaussian Elimination for finding Mutants...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Compeleted.
	The size of Matrix is:
		No. of Rows=3
		No. of Columns=9
Appling Gaussian Elimination for finding Mutants...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Compeleted.
	The size of Matrix is:
		No. of Rows=9
		No. of Columns=4
Appling Gaussian Elimination to check solution coordinate...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Completed.
	The size of Matrix is:
		No. of Rows=9
		No. of Columns=4
Appling Gaussian Elimination to check solution coordinate...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Completed.
	No. of New Mutants found = 0
	The size of Matrix is:
		No. of Rows=7
		No. of Columns=14
Appling Gaussian Elimination for finding Mutants...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Compeleted.
	The size of Matrix is:
		No. of Rows=14
		No. of Columns=8
Appling Gaussian Elimination to check solution coordinate...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Completed.
	The size of Matrix is:
		No. of Rows=14
		No. of Columns=8
Appling Gaussian Elimination to check solution coordinate...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Completed.
	No. of New Mutants found = 2
	The total No. of Mutants found are = 2
	The No. of Mutants of Minimum degree (Mutants used) are = 2
	The size of Matrix is:
		No. of Rows=9
		No. of Columns=10
Appling Gaussian Elimination for finding Mutants...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Compeleted.
	The size of Matrix is:
		No. of Rows=10
		No. of Columns=8
Appling Gaussian Elimination to check solution coordinate...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Completed.
	The size of Matrix is:
		No. of Rows=10
		No. of Columns=8
Appling Gaussian Elimination to check solution coordinate...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Completed.
	No. of New Mutants found = 0
	The size of Matrix is:
		No. of Rows=7
		No. of Columns=10
Appling Gaussian Elimination for finding Mutants...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Compeleted.
	The size of Matrix is:
		No. of Rows=10
		No. of Columns=8
Appling Gaussian Elimination to check solution coordinate...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Completed.
	The size of Matrix is:
		No. of Rows=10
		No. of Columns=8
Appling Gaussian Elimination to check solution coordinate...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Completed.
	No. of New Mutants found = 0
	The size of Matrix is:
		No. of Rows=22
		No. of Columns=14
Appling Gaussian Elimination for finding Mutants...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Compeleted.
	The size of Matrix is:
		No. of Rows=14
		No. of Columns=13
Appling Gaussian Elimination to check solution coordinate...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Completed.
	The size of Matrix is:
		No. of Rows=14
		No. of Columns=13
Appling Gaussian Elimination to check solution coordinate...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Completed.
x[4] = NA
	Please Check the uniqueness of solution.
	The Given system of polynomials does not
	seem to have a unique solution or it has
	no solution over the finite field F2.


See also

CharP.MXLSolve

Introduction to CoCoAServer

Introduction to Groebner Basis in CoCoA

CharP.GBasisF2

CharP.XLSolve

CharP.IMXLSolve

CharP.MNLASolve





Retrieved from "http://apcocoa.uni-passau.de/wiki/index.php?title=ApCoCoA-1:CharP.IMNLASolve&oldid=11770"