Difference between revisions of "ApCoCoA-1:CharP.MNLASolve"

From ApCoCoAWiki
Line 1: Line 1:
 
<command>
 
<command>
−
     <title>CharP.GBasisF2</title>
+
     <title>CharP.MNLASolve</title>
−
     <short_description>Computing the unique <tt>F_2-</tt>rational zero of a given polynomial system over <tt>F_2</tt>.</short_description>
+
     <short_description>Computes the unique <tt>F_2-</tt>rational zero of a given polynomial system over <tt>F_2</tt>.</short_description>
 
<syntax>
 
<syntax>
 
CharP.MNLASolve(F:LIST):LIST
 
CharP.MNLASolve(F:LIST):LIST
Line 9: Line 9:
  
 
<par/>
 
<par/>
−
This function computes the unique zero in <tt>F_2^n</tt> of a polynomial system over <tt>F_2 </tt>. It uses Mutant NLA<tt>-</tt>Algorithm to find the unique zero. The Mutant NLA<tt>-</tt>Algorithm generates a sequence of linear systems to solve the given system. The Mutant NLA<tt>-</tt>Algorithm can find the unique zero only. If the given polynomial system has more than one zeros in <tt>F_2^n </tt> 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 Mutant NLA<tt>-</tt>Algorithm is the NLA<tt>-</tt>Algorithm with mutant strategy. It uses <ref>linalg.EF</ref> for gaussian elimination.
+
This function computes the unique zero in <tt>F_2^n</tt> of a polynomial system over <tt>F_2 </tt>. It uses Mutant NLA-Algorithm to find the unique zero. The Mutant NLA-Algorithm generates a sequence of linear systems to solve the given system. The Mutant NLA-Algorithm can find the unique zero only. If the given polynomial system has more than one zeros in <tt>F_2^n </tt> 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 Mutant NLA-Algorithm is the NLA-Algorithm with mutant strategy. It uses <ref>LinAlg.EF</ref> for gaussian elimination.
  
  
Line 363: Line 363:
 
     <see>CharP.IMXLSolve</see>
 
     <see>CharP.IMXLSolve</see>
 
     <see>CharP.IMNLASolve</see>
 
     <see>CharP.IMNLASolve</see>
−
   
 
−
 
−
 
 
   </seealso>
 
   </seealso>
  
Line 374: Line 371:
 
     </types>
 
     </types>
  
−
     <key>charP.GBasisF2</key>
+
     <key>charP.mnlasolve</key>
−
     <key>GBasisF2</key>
+
     <key>mnlasolve</key>
 
     <key>finite field</key>
 
     <key>finite field</key>
 
     <wiki-category>Package_charP</wiki-category>
 
     <wiki-category>Package_charP</wiki-category>
 
   </command>
 
   </command>

Revision as of 14:15, 14 December 2010

CharP.MNLASolve

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

Syntax

CharP.MNLASolve(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 Mutant NLA-Algorithm to find the unique zero. The Mutant NLA-Algorithm generates a sequence of linear systems to solve the given system. The 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 Mutant NLA-Algorithm is the NLA-Algorithm with mutant strategy. It uses LinAlg.EF for gaussian elimination.


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

  • @return 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.MNLASolve(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.
	The No. of 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.015
-------------------------------
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.
	The No. of Mutants found = 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.016
-------------------------------
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.
	The No. of 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.MNLASolve(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.
	The No. of Mutants found = 0
	The size of Matrix is:
		No. of Rows=15
		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=12
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=12
Appling Gaussian Elimination to check solution coordinate...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Completed.
	The No. of Mutants found = 4
	The size of Matrix is:
		No. of Rows=27
		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.
	The No. of Mutants found = 0
	The size of Matrix is:
		No. of Rows=12
		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.016
-------------------------------
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.
	The No. of Mutants found = 0
	The size of Matrix is:
		No. of Rows=19
		No. of Columns=15
Appling Gaussian Elimination for finding Mutants...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Compeleted
	The size of Matrix is:
		No. of Rows=15
		No. of Columns=14
Appling Gaussian Elimination to check solution coordinate...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Completed.
	The size of Matrix is:
		No. of Rows=15
		No. of Columns=14
Appling Gaussian Elimination to check solution coordinate...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Completed.
	The No. of Mutants found = 0
	The size of Matrix is:
		No. of Rows=14
		No. of Columns=15
Appling Gaussian Elimination for finding Mutants...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Compeleted
	The size of Matrix is:
		No. of Rows=15
		No. of Columns=14
Appling Gaussian Elimination to check solution coordinate...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Completed.
	The size of Matrix is:
		No. of Rows=15
		No. of Columns=14
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.IMNLASolve





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