Carl Love

Carl Love

28055 Reputation

25 Badges

12 years, 361 days
Himself
Wayland, Massachusetts, United States
My name was formerly Carl Devore.

MaplePrimes Activity


These are replies submitted by Carl Love

This is the third time that you've posted this problem since March 7---only 1-1/2 months. Three of the top seven responders on this site have already given you input. Understand that no one here can help you further. It's not that this problem is uninteresting or that you've inadequately described it. I find it interesting. It's just too hard. Perhaps it's time to accept that this problem can only be solved numerically, not symbolically. There're a great many such problems. Do you have some reason to believe that this problem can be solved symbolically?

If you make progress on this problem, then post a followup to one of your previous threads. Don't make a new Question unless it's truly new. If you encounter any Maple-related issues in your investigations, then please do post them as new Questions. For example, your Question "D meaning in Maple" was a fine Question even though it involved this same problem.

Try posting in Stack Exchange's Math Overflow forum. That's their forum for research-level problems.

If I've misinterpretted your intent, and you actually do want to make a numerical comparison of these five functions, then ignore my comments above and please accept my apology: I was mistakenly inferring your intent based on your previous posts about this problem. There're numerous ways that we can use Maple to make a numerical comparison.

 

@c4meleon 

If you're truly sorry for what you did, then you will put back the original Question with the code that was in it, or some close approximation of that, and change the title to something appropriate. And if you're not sorry, then I'll never respond to your posts again.

And, no, I don't respect you, yet. But I could come quickly around to it if you come correct.

@testht06 

You wrote:

Of course I known R^4 = M and I checked by simply comnand Expand~(R^4) mod p;. But the problem is that if I excuted Your proc with M:= [ [x^2, x,1,1], [x^3,x^2+x,x^2+1,x^2+x],[x^3+x+1,x^3+x^2+x, x^3+x,x^2+x],[x,x,x^3+x^2+x+1, x^3+x+1], but not receive R= [[0,1,0,0],[0,0,1,0],[0,0,0,1],[1,1,x,x^2].

But using the values for and M that you give in the above paragraph R^4 is NOT equal to M!! That is clearly shown by the easy computation Expand~(R^4) mod p---a computation that doesn't involve my program at all. You say "Of course" and "I checked ... Expand~(R^4) mod p." Well, then attach a worksheet showing that you checked. Because if you're getting that R^4 = M, then there's a serious bug in Maple---a bug in basic matrix multiplication that's nearly beyond belief. I even did the matrix multiplication by hand, and I did not get M.

And with the following matrix

M:= < x^3+x^2+x, x+1, x^3+x+1, x^5+x+1; 
 x, x, 1, x+1; 
 x^3+x^2+1, 1, x^3+x+1, x^5+x^3; 
 x^4+x^3+x, x^2+x, x^4+x^2+1, x^6+x^2+x+1 >:

also not receive R=[[0,1,0,x],[1,0,1,0],[x,0,1,3],[1,0,1,x^2]], while R^3 = M

In this case it is indeed true that R^3 = M. But nth roots are of course not generally unique. In the cases that we've dealt with so far, the fourth roots of the eigenvalues were unique. That means that R was uniquely determined. In the case at hand, each eigenvalue has three distinct cube roots. That means that M has 3^4 = 81 different cube roots. Now, if you want, I could search through all 81 cube roots for those that can be represented in the original field. But that can be a lengthy search---which quickly grows much longer as ROOT and the order of the matrix increases.

Moreover, the input of this proc is any matrix, need to find R (R is completely unknown)

Uh-uh. First we work out all the bugs, kinks, and issues in the worksheet version. Then I'll make it into an actual proc procedure that will work for an arbitrary finite-field matrix M and positive integer ROOT.

 

@rbd66 

After or under makes no difference. Please post the worksheet showing it not working. Here's my copy of the worksheet showing the command working.

Earthquake_2_eval.mw

@Markiyan Hirnyk Yes, I forgot about the Explore command, and I agree with you.

DON'T EVER DELETE OR EDIT OUT THE BODY OF OR CHANGE THE TITLE OF YOUR ORIGINAL QUESTION AFTER IT HAS RESPONSES!!!! YOU HAVE JUST MADE THIS WHOLE THREAD WORTHLESS FOR OTHER/FUTURE READERS!!! IT'S NOT ALL ABOUT YOU AND YOUR QUESTION! HAVE SOME RESPECT FOR THE OTHER READERS AND FOR THE WRITERS WHO TOOK THE TIME TO RESPOND TO YOU.

Hello, and welcome to MaplePrimes.

1. Your boundary conditions use a parameter q which your post doesn't give the numeric value of. I can't debug this without that q.

2. I note that your f and g are not coupled; they can be solved separately. So my first step to debugging this would be to try to solve them separately.

3. pdsolve(...numeric) is often very sensitive to its optional arguments spacesteptimestep, etc. I've often gotten results that were complete garbage (as you're getting) on the first try that could be corrected by adjusting the options.

4. What is the significance of your boundary positions -100 and 100? Are they stand-ins for infinity? If yes, then try making those -10 and 10 or -5 and 5. Get it working for those values first, and then, if need be, gradually spread them out.

5. In the future, please post your code as plaintext and/or as an attached worksheet. (Plaintext is the format that you used for the parameters r0 and theta0.) This is so that no-one has to retype it. To attach a worksheet, use the green uparrow tool, which is the last item on the second row of the toolbar in the MaplePrimes editor.

@matmxhu 

Your "catch string" should not include the first part, "Error, (in fsolve/polyill) "; it should be simply "time expired". So try this:

g:= proc()  [solve(eq)] end proc:

try
     sols:= timelimit(300, g())
catch "time expired":
     sols:= SolveEquations(eq)
end try;

@testht06 

No, it doesn't check out. You can see for yourself simply by computing R^4 using the proposed fourth root as the R

R:= <0,1,0,0;
          0,0,1,0;
          0,0,0,1;
          1,1,x,x^2>:

Expand~(R^4) mod p;

@testht06 

You wrote:

Please help me convert the entries of R (and R^4) from GF(2^16) back to GF(2^8).

Okay, it's done, amazingly enough. And R has a very simple representation in the original field. This conversion back to the original field will not be possible in the general case. I had to construct an explicit field isomorphism element by element to do this. I could not come up with an algebraic trick for it. I hope that someone here can help me with that.

I think, GF(2^8) is the sub set of GF(2^16).

Yes, but that subset is not a subfield, in particular it is not the subfield of GF(2^16) which is isomorphic to our original GF(2^8). To see that such a situation is not even possible, consider this: y^7 is a member of that subset, but its square, y^14, is not. So the subset is not closed under multiplication and is thus not a subfield.

And while convert R and R^4 back to GF(2^8), the entries ≤ 255 will be not changed

No, they must be changed, for the reason in the preceding paragraph. The only elements that can stay the same are the members of the prime subfield---in this case just 0 and 1.

Furthermore, for the calculation of the roots of the factor (t2 +231t +30), can You choose an irreducible polynomial ext2 over GF(2^8)? (ie ext2 = t2 + at + b, where a, b in GF(2^8). GF((28)2 is the composition field)

Well t^2+231T+30 itself is irreducible, and that is what I chose, essentially. But the only way that Maple will work with a composite field is by "flattening" the representation from (2^8)^2 to 2^16 via Primfield.

Here is the new worksheet, which is mostly the same as the previous worksheet, but it has isomorphism at the bottom and the conversion of R back to the original field.



Fractional powers of matrices over finite fields

Author: Carl J Love, 2015-Apr-18.

restart:

Define a field extension for GF(2^8) using an irreducible polynomial of degree 8.

p:= 2:  ext1:= Z^8+Z^4+Z^3+Z+1:  d:= degree(ext1, Z):

Verify irreducibility:

Factors(ext1) mod p;

[1, [[Z^8+Z^4+Z^3+Z+1, 1]]]

Coefficients in the new field are expressed as polynomials in abstract roots of the extending polynomial expressed via the RootOf function. We wish to write and to see this root as a simple variable rather than as a complicated RootOf function, so we use alias.

alias(x= RootOf(ext1)):

We will extract the fourth root of the matrix below. First we will extract its eigenvalues in this field, and then we'll construct a splitting field to get the remaining eigenvalues.

ROOT:= 4:

M:= < 1,     x,             1,           x^2;
      x^2,   x^3+1,         x^2+x,       x^4+1;
      x^4+1, x^5+x^2+x,     x^4+x^3,     x^6+x;
      x^6+x, x^7+x^4+x^2+1, x^6+x^5+x^2, x^3+x+1 >:

C:= Charpoly(M,t) mod p;

t^4+(x^3+x+1+x^4)*t^3+t^2+x^4*t+1

The field's elements can be compactly represented as integers by a natural base-p encoding scheme. This is for our viewing purposes only; it is not used for computation.

encode:= (ex,x)-> eval(ex, x= p):

encode(C,x);

t^4+27*t^3+t^2+16*t+1

CF:= Factors(C) mod p;

[1, [[x^7*t+x^6*t+x^5*t+x^4+x^3+x^2*t+x^2+x*t+t^2+x+t, 1], [x^5+x^2+t+1, 1], [x^7+x^6+x^4+x^3+t+1, 1]]]

encode(CF,x);

[1, [[t^2+231*t+30, 1], [37+t, 1], [217+t, 1]]]

So we have two eigenvalues in our field (represented as 217 and 37 in the encoding scheme), and two more that are the roots of the irreducible quadratic.

 

Extract the nonlinear irreducible parts (this command works even if there is more than one irreducible factor):

irr:= map(collect, select(q-> degree(q,t) > 1, map2(op,1,CF[2])), t);

[t^2+(x^7+x^6+x^5+x^2+x+1)*t+x^4+x^3+x^2+x]

encode(irr,x);

[t^2+231*t+30]

q:= irr[1]:

Now construct the splitting field that contains q's roots.

alias(z= RootOf(q)):

PF:= Primfield({x,z}) mod p:

Extract the new degree 16 field extension:

ext2:= (indets(PF, 'RootOf'(anything)) minus {x,z})[];

RootOf(_Z^16+_Z^13+_Z^10+_Z^9+_Z^2+_Z+1)

Note that ext2 is a randomly chosen irreducible (mod 2) polynomial of degree 16. If you execute the Primfield command again, you may get a different polynomial. The important thing is how the old field's entries are expressed in the new field. All these relationships are stored in PF. We compactify the visual representation of the relationships with a new alias.

alias(y= ext2):

PF;

[[y = z^15*x+z^14+z^11+z^8+z^4+z^3+z], [z = y^15+y^14+y^8+y^5+y^4+y^3+y^2, x = y^15+y^13+y^11+y^10+y^8+y^7+y^6+y^4+y^2+y]]

The first equation is not of much use to us here. One of the others expresses one of the roots of q,which we named z, in the new field. The other expresses the old field extension x in terms of the new, y.

newx:= eval(x, PF[2]);

y^15+y^13+y^11+y^10+y^8+y^7+y^6+y^4+y^2+y

Now re-express q in the new field.

newq:= collect(Expand(eval(q, x= newx)) mod p, t);

t^2+(y^13+y^12+y^11+y^9+y^8+y^7+y^5+y^4+y^2+y)*t+y^15+y^13+y^11+y^7+y^6+y^5+y^2+y+1

encode(%,y);

t^2+15286*t+43239

Now get both roots:

Rq:= Roots(newq) mod p;

[[y^15+y^14+y^8+y^5+y^4+y^3+y^2, 1], [y^15+y^14+y^13+y^12+y^11+y^9+y^7+y^3+y, 1]]

encode(%,y);

[[49468, 1], [64138, 1]]

We can see that one of the roots is, of course, the z. Now verify that the second root is the first one raised to the 2^8 power:

Expand(eval(z, PF[2])^(p^d)) mod p;

y^15+y^14+y^13+y^12+y^11+y^9+y^7+y^3+y

encode(%,y);

64138

Re-express the original matrix in the newly extended field.

newM:= Expand~(eval(M, x= newx)) mod p:

Now I need the Eigenvalues and Eigenvector procedure that I presented for an earlier Question.

`mod/Eigenvalues`:= proc(M::Matrix(square), p::posint)
     local x;
     Roots(Charpoly(M, x) mod p) mod p
end proc:

`mod/Eigenvector`:= proc(M::Matrix(square), lambda, p::posint)
#Returns an eigenvector of M associated with the eigenvalue lambda.
uses LA= LinearAlgebra;
local
     n:= op([1,1], M),
     rank, t,
     sol:= Linsolve(M - lambda*LA:-IdentityMatrix(n), Vector([0$n]), rank, t) mod p
;
     if rank=n then
          error "Second argument must be an eigenvalue of the first."
     end if;
     eval(sol, indets(sol, specindex(posint,t))[]= 1)
end proc:

eigs:= Eigenvalues(newM) mod p;

[[y^15+y^14+y^8+y^5+y^4+y^3+y^2, 1], [y^15+y^14+y^13+y^12+y^11+y^9+y^7+y^3+y, 1], [y^15+y^14+y^11+y^10+y^9+y^7+y^2+y, 1], [y^13+y^12+y^11+y^9+y^8+y^7+y^2+y+1, 1]]

We know that this matrix will pass the following check, but the check will be needed in general.

if nops(eigs) <> op([1,1],M) then
    error "Case of repeated or missing eigenvalues not handled"
end if;

Construct the matrix P of eigenvectors:

P:= `<|>`(seq(Eigenvector(newM, lambda[1]) mod p, lambda= eigs)):

Compute the roots of the eigenvalues.

ROOTs:= map(lambda-> Roots(t^ROOT - lambda[1]) mod p, eigs);

[[[y^15+y^14+y^10+y^9+y^6+y^5+y^4+y^2+y, 4]], [[y^15+y^14+y^11+y^10+y^5+y^4+y^3+y^2+y+1, 4]], [[y^10+y^9+y^8+y^4+y, 4]], [[y^14+y^13+y^11+y^9+y^8+y^3+y, 4]]]

Check that each eigenvalue has an appropriate root in the current field.

if [] in {ROOTs[]} then
     error "Case of root of eigenvalue not existing in the current field not yet implemented"
end if:

Construct the diagonal matrix of the roots of the eigenvalues

Diag:= LinearAlgebra:-DiagonalMatrix(map(x-> op(1,op(x)), ROOTs)):

Construct the "root" matrix

R:= Expand~(P.Diag.(Inverse(P) mod p)) mod p;

R := Matrix(4, 4, {(1, 1) = 0, (1, 2) = 1, (1, 3) = 0, (1, 4) = 0, (2, 1) = 0, (2, 2) = 0, (2, 3) = 1, (2, 4) = 0, (3, 1) = 0, (3, 2) = 0, (3, 3) = 0, (3, 4) = 1, (4, 1) = 1, (4, 2) = y^15+y^13+y^11+y^10+y^8+y^7+y^6+y^4+y^2+y, (4, 3) = 1, (4, 4) = y^14+y^13+y^10+y^9+y^6+y^4+1})

Verify that R is indeed the root of the starting matrix.

Expand~(R^ROOT - newM) mod p;

Matrix(4, 4, {(1, 1) = 0, (1, 2) = 0, (1, 3) = 0, (1, 4) = 0, (2, 1) = 0, (2, 2) = 0, (2, 3) = 0, (2, 4) = 0, (3, 1) = 0, (3, 2) = 0, (3, 3) = 0, (3, 4) = 0, (4, 1) = 0, (4, 2) = 0, (4, 3) = 0, (4, 4) = 0})

We wish to convert---to whatever extent possible---the entries of these matrices from their representations in GF(2^16) back to GF(2^8). To this end, we explicitly construct a field isomorphism between GF(2^8) and the subfield of GF(2^16) that it is isomorphic to. Unfortunately, this is done by a direct element-by-element mapping: Every element of GF(2^8) is converted to its GF(2^16) form and then this mapping is inverted. I wish that I knew an algebraic trick to do this, but I can't come up with anything.

X:= <seq(x^k, k= 0..d-1)>:
Y:= Expand~(<seq(newx^k, k= 0..d-1)>) mod p:

assign(((C-> Iso(Expand(C.Y) mod p) = C.X)@`<,>`)~(combinat:-permute([seq(k$d, k= 0..p-1)], d))):  

Apply the isomorphism to R:

R:= Iso~(R);

R := Matrix(4, 4, {(1, 1) = 0, (1, 2) = 1, (1, 3) = 0, (1, 4) = 0, (2, 1) = 0, (2, 2) = 0, (2, 3) = 1, (2, 4) = 0, (3, 1) = 0, (3, 2) = 0, (3, 3) = 0, (3, 4) = 1, (4, 1) = 1, (4, 2) = x, (4, 3) = 1, (4, 4) = x^2})

Once again, verify that R^4 is the starting matrix, this time in its original form.

Expand~(R^ROOT - M) mod p;

Matrix(4, 4, {(1, 1) = 0, (1, 2) = 0, (1, 3) = 0, (1, 4) = 0, (2, 1) = 0, (2, 2) = 0, (2, 3) = 0, (2, 4) = 0, (3, 1) = 0, (3, 2) = 0, (3, 3) = 0, (3, 4) = 0, (4, 1) = 0, (4, 2) = 0, (4, 3) = 0, (4, 4) = 0})

 



Download Matrix_powers_finite_field.mw

 

@matmxhu 

This is a new question completely unrelated to the theme of this thread: limiting the time of processes! Please post as a new Question, a new thread!

@tomleslie 

Yes, I find it very surprising that frem has no symbolic capability and that it cannot be evaluated by evalhf. My solution seems, so far, to correct all problems.

You wrote:

[A]ll "solutions" I have seen are based on the premise: please don't check the arguments to frem() until floats are actually presented.

My (second) solution does not rely on that.

[I]f frem(x,y) when presented with one or two symbolic arguments. simply returned frem(x,y), then the issue would be avoided.

It is trivial to write an frem variant that does that, but it wouldn't solve all problems. For example, you wouldn't be able to symbolically integrate or differentiate it. My solution relies on the fact that floor is fully symbolic.

@patient For what it's worth (which I don't know at this point), the FindSingularity procedure that I gave will work for backwards integration, say using 0 as the initial point and integrating towards -1. No modification is needed---simply call FindSingularity(sol, -1).

@Preben Alsholm 

Try a time comparison of your procedural dsolve with my symbolic version of frem:

Frem:= (x,y)-> x - y*floor(x/y+1/2);

Ironically, Frem can be evaluated by evalhf, but frem can't be. For that reason, I think that it'll be faster.

@Axel Vogt 

What you called "acer's trick" was my trick. It seems that the setting of Digits determines whether declaring a method is needed. At Digits = 10, no method is needed. My guess is that the native Maple methods can't guarantee the accuracy at the higher setting.

Regarding the symbolic integration, see my new Answer about a symbolic equivalent to frem. It integrates easily.

First 492 493 494 495 496 497 498 Last Page 494 of 709