Items tagged with algorithm algorithm Tagged Items Feed

I want to test linearly dependence of a polynomial f on a list of polynomials F by additional condition on parametric coefficients of linear parametric polynomial (linear for variables not parameters). Please note that:

  1. The polynomialand the members of are always homogenous in the variables.
  2. The coefficients of f, the coefficients of the members of F are all always polynomials in the parameters or contant and the members of N and W are all always polynomials in the parameters.

 

For example let

and

(a,b,c,d,e,h are parameters and A1,A2,A3 are variables).

If I use PolyLinearCombo(F,f,{A1,A2,A3}) (see http://www.mapleprimes.com/questions/204469-How-Can-I-Find-The-Coefficients-Of-Linear#comment217621)then its output is false,[].

Now we let to condition sets for parameters as the following:

N:=[ebc+ahd]

W:=[a,c]

The elements of N must be zero means that ebc+ahd=0

and the elements of W are non-zero that is a<>0 and c <>0.

Let a=b=c=d=h=1 and e=-1. This specialization satisfy in the above condition sets N and W. By this specialization we have:

and

Now if I use PolyLinearCombo(F,f,{A1,A2,A3}) then its output is true,[-1,1].

By this additional two condition sets I have to check that whether f is linearly independent of F or not. How can I do this without specialization? In fact I want an algorithm that its input is (null condition N, not-null condition W, list of polynomials F, a polynomial f, the set of variables) and its output is true and coefficients if f is linearly dependent of F w.r.t. null and not-null conditions N and W, else its output is false.

If the name of new procedure is ExtPolyLinearCombo and 

N:=[ebc+ahd]

W:=[a,c]

I want the output of

ExtPolyLinearCombo(N,W,F,f,{A1,A2,A3}) be true,[coefficients]

Thank you very much in advance.

 

 

Hi all,

Please help in writing finite difference algorithm for a nonlinear PDE using Maple.

for a[j], b[j] known at time n, I want to compute A[j]  for a[j] at time n+1 according to the equation below

EQs:=A[j]-theta*tau*(A[j-1]-2*A[j]+A[j+1])=a[j]+sqrt(a[j])*b[j]*h^2/tau+(1-theta)*tau*(a[j-1]-2*a[j]+a[j+1]) ;

Thanks in advance.

I am trying to understand how maple "isprime" algorithm works. But I can't find anywhere what special_primes means.

 

 showstat(isprime);

isprime := proc(n)
local btor, nr, p, r;
   1   if not type(n,'integer') then
   2     if type(n,('complex')('numeric')) then
   3       error "argument must be an integer"
         else
   4       return 'isprime(n)'
         end if
       end if;
   5   if n < 2 then
   6     return false
       elif member(n,isprime:-special_primes) then
   7     return true
       elif igcd(2305567963945518424753102147331756070,n) <> 1 then
   8     return false
       elif n < 10201 then
   9     return true
       elif igcd(8496969489233418110532339909187349965926062586648932736611545426342203893270769390909069477309509137509786917118668028861499333825097682386722983737962963066757674131126736578936440788157186969893730633113066478620448624949257324022627395437363639038752608166758661255956834630697220447512298848222228550062683786342519960225996301315945644470064720696621750477244528915927867113,n) <> 1 then
  10     return false
       elif n < 1018081 then
  11     return true
       else
  12     r := gmp_isprime(n);
  13     if not r or n <= 5000000000 then
  14       return r
         end if;
  15     nr := igcd(408410100000,n-1);
  16     nr := igcd(nr^5,n-1);
  17     r := iquo(n-1,nr);
  18     btor := modp(('power')(2,r),n);
  19     if cyclotest(n,btor,2,r) = false or irem(nr,3) = 0 and cyclotest(n,btor,3,r) = false or irem(nr,5) = 0 and cyclotest(n,btor,5,r) = false or irem(nr,7) = 0 and cyclotest(n,btor,7,r) = false then
  20       return false
         end if;
  21     if isqrt(n)^2 = n then
  22       return false
         end if;
  23     for p from 3 while numtheory:-jacobi(p^2-4,n) <> -1 do
  24       NULL
         end do;
  25     return evalb(TraceModQF(p,n+1,n) = [2, p])
       end if
end proc

I would like to pay attention to an article by David Austin "The Stable Marriage Problem and School Choice"

Here is its inroduction:

" Every year, 75,000 New York City eighth graders apply for admission to one of the city's 426 public high schools. Until recently, this process asked students to list five schools in order of preference. These lists were sent to the schools, who decided which applicants to accept, wait-list, or reject. The students were then notified of their status and allowed to accept only one offer and one position on a waiting list. After the students had responded to any offers received, schools with unfilled positions made a second round of offers, and this process continued through a concluding third round.

This process had several serious problems. At the end of the third round of offers, nearly half of the students, usually lower-performing students from poor families, had not been accepted into a school. Many of these students waited through the summer only to learn they had been matched with a school that was not on their list of five schools.

This process also encouraged students and their parents to think strategically about the list of schools they submitted. Students that were rejected by the school at the top of their list might find that their second-choice school had no vacancies in the second round of offers. This made it risky for many students to faithfully state their true preferences, a view encouraged by the Education Department's advice that students "determine what your competition is" before creating their lists of preferred schools.

Lastly, schools would often underrepresent their capacity hoping to save positions for students who were unhappy with their initial offerings.

In the end, the process couldn't place many students while it encouraged all parties, both students and schools, to strategically misrepresent themselves in an effort to obtain more desirable outcomes not possible otherwise. Widespread mistrust in the placement process was a natural consequence.

Using ideas described in this column, economists Atila Abdulkadiroglu, Parag Pathak, and Alvin Roth designed a clearinghouse for matching students with high schools, which was first implemented in 2004. This new computerized algorithm places all but about 3000 students each year and results in more students receiving offers from their first-choice schools. As a result, students now submit lists that reflect their true preferences, which provides school officials with public input into the determination of which schools to close or reform. For their part, schools have found that there is no longer an advantage to underrepresenting their capacity.

The key to this new algorithm is the notion of stability, first introduced in a 1962 paper by Gale and Shapley. We say that a matching of students to schools is stable if there is not a student and a school who would prefer to be matched with each other more than their current matches. Gale and Shapley introduced an algorithm, sometimes called deferred acceptance, which is guaranteed to produced a stable matching. Later, Roth showed that when the deferred acceptance algorithm is applied, a student can not gain admittance into a more preferred school by strategically misrepresenting his or her preferences.

This column will present the game-theoretic results contained in the original Gale-Shapley paper along with Roth's subsequent analysis. Pathak calls the deferred acceptance algorithm "one of the great ideas in economics," and Roth and Shapley were awarded the 2012 Nobel Prize in economics for this work"

It would be nice to realize that in Maple.

 

 

Hello,

I have a question. I have to compare the times and steps taken by an algorithmus (which contents a loop).

So for time there is the time()-function, right? And is there any similar function for the steps taken?

So far i use a variable increasing by 1 each time, but i think there is an more elegant way to do it, which I just don't know.. :D

 

Thanks for any help!

 

I need to write a procedure that does the following :

Write a procedure quadsum whose input is an integer n and whose output is a list of pairs of solutions [x,y] to the above formula.

Your procedure should implement the following algorithm.

1 Initialization
Set
"mylist = []."

Start at
x = 0
and
y = 0.

2 Phase A
Increment both
x
and
y
until
"x^2+y^2 >=n."

Phase B
Repeat the following until
x^2>n

If you are above the circle
x^2 + y^2 = n
then go down in unit steps until you are on or below the circle.

If you are on the circle, add the point to the list
"mylist. "

If you are on or below the circle
x^2 + y^2 = n
then go one step to the right. My procedure is as follows: but it runs into an infinite loop(most probably because of the while loop defined inside the while loop). What am I doing incorrectly?

I have atta

 

Hi there,

I'm trying to simulate an stochastic SIR model following the Gillespie algorithm, as described here [1].

 

When trying to update each process' probabilities, it looks like Maple is not updating their values. Although each element of the lists S, I and R is updated the ai lists are not updated.

For example, for a given index i

a2[i]:= m*S[i]:

takes the same value for every i, regardless of the value of S[i].

Can anybody tell why this is happening or what's wrong with the worksheet? This is the attempt: MaplePrimes_SIR_model_simulation_Gillespie_algorithm.mw

 

On the other hand, I tried making things more clear through a couple of procedures. However, when it comes to the point where a random number with an exponential distirbution is computed:

Rexp := RandomVariable(Exponential(mu)):

it looks like Maple is unable to evaluate mu. But having a look at the Variables explorer, it has a defined value, indeed.

So what's wrong in the worksheet? Thi is the attempt: MaplePrimes_SIR_model_simulation_Gillespie_algorithm.mw

 

Thanks,

jon

[1] http://www.biosym.uzh.ch/modules/models/ETHZ/StochasticSimulation/sir_stoch.xhtml

Currently calculations: equations, regression analysis, differential equations, etc; to mention a few of them; are developed using traditional methods ie even are proposed and solved by hand and on paper. In teaching our scientists and engineers use the chalkboard as a way to reach students and enable them to solve their calculation. To what extent Maple contributes to research on new mathematical models applied science and engineering ?. Maplesoft appears as a proposal to resolve problems with our traditional proposed intelligent algorithms, development process, embedded components, and not only them but also generates type applications for Apple ipad tablets signature. Based on the computer algebra system Maple Maplesoft gives us the package which works exactly like we were on our work. I will show how mathematics is developed from a purely basic to reach modeling differential equations applied to education and engineering. Also visualizare current techniques for developing applications for mobile devices.

link: https://www.youtube.com/watch?v=FdRUSgfPBoc

 

ECI_2015.pdf

Atte.

Lenin Araujo Castillo

Physics Pure

Computer Science

Dear Maple Experts,

i am new to maple and I am trying to write a maple algorithm in order to calculate the GCD of two functions. 

I have defined the two functions and written the algorithm, but I get an error "Unable to Parse".

Here is my code:

restart; with(Algebraic); with(LinearAlgebra[Generic]); with(RegularChains); with(FastArithmeticTools); with(ChainTools); interface(rtablesize = 15);

f := (y^2-1)*((y+1)*x^4+(y^2-1)*x^3+(y^3-1)*x^2+(y^4-1)*x+y^5-1);

g := (y-1)*x^5+(y^2-1)*x^4+(y^3-1)*x^3+(y^4-1)*x^2+(y^5-1)*x+y^6-1;

SubRes:=proc(f,g,var): local  i,a, delta, beta, psi: if degree(f,var)<degree(g,var) then a[0]:=Algebraic:-PrimitivePart(g,var): a[1]:=Algebraic:-PrimitivePart(f,var): else a[0]=Algebraic:-PrimitivePart(f,var): a[1]:=Algebraic:-PrimitivePart(g,var): fi: delta[0]:=degree(a[0],var)-degree(a[1],var): beta[2]:=(-1)^((delta[0]+1)): psi[2]:=-1: i:=1: while a[i]<>0 do a[i+1]:=(prem(a[i-1], a[i], var))/(beta[i+1]): delta[i]:=degree(a[i],var)-degree(a[i+1], var): i:=i+1: psi[i+1]:=((-lcoeff(a[i-1],var))^((delta[i-2])))*((psi[i])^((1-delta[i-2]))): beta[i+1]:=-lcoeff(a[i-1],var)*(psi[i+1])^((delta[i-1])): od: print("Last Non-Zero Subresultant: ", sort(simplify(a[i-1])),y): return (Algebraic:-PrimitivePart(a[i-1],var)): end proc

and I get this error:

Error, unable to parse

Would you kindly help me to fix this issue?

Kind Regards,

Ash

 

So the pseudocode I'm trying to translate into maple is for the greedy vertex coloring algorithm.

The pseudo code is:

Initialize:
1. for i = 1 to n do
2. f[i] := 0 (: no color assigned yet to vertex i :)
3. end(for)
Main loop:
4. for i = 1 to n do
5. let f[i] be the smallest positive integer
which is not in the set {f(j) : j ∈ adj[i]}
6. end(for)
7 return f

 

The closest I've gotten though is:

greedy := proc (G)

local i, j, n, k, L::list;

description "Take simple graph G and return a coloring of the vertices with at most Delta(G)+1 colors";

n := nops(Vertices(G));
L := [seq(x, i = 1 .. n)];
L := subsop(1 = c(1), L);
j := 1;
for i from 2 to n do
L[Vertices(G)[i]] := c(0)
end do;

for i from 2 to n do
   for k to i do
        if member(Vertices(G)[i], Neighbors(G, Vertices(G)[k])) then j := j+1
       end if; 
   end do;
L[Vertices(G)[i]] := c(j)
end do;
return L;
end proc;

Basically my procedure is returning more than delta+1 colors for most graphs, how can I edit it to fix this? I'm guessing the problem is somewhere in my nested loops. Also, I cannot use commands like greedycolor or isvertexcolorable. Thanks.

 

Having solution of an inequations system, is there a way/function/algorithm to find a particular numeric solution (as simplex[minimize] can do) ?

ex:

Q := {1 < x - y, x + y < 1};

R := solve(Q);

      { x < 1 - y, y < 0, y + 1 < x }

manually it's easy to find some numeric solutions:


      y = -1, x = 1
      y = -2, x = 0

but I need an automatic way.

Thank you for your help
s.py

 

Hi all

Can anybody suggest an algorithm allowing to detect, that two matrices of the same size can be obtained each from other by permutations of rows and columns? Maybe, such an algorithm there exists in LinearAlgebra package?

Good day everyone, please help in writing finite difference algorithm for these coupled nonlinear ODE. See it here Algorithm.mw 

#page 320 and 322 of book Singular introduction to commutative algebra

it return too many recursion 

 

hilbertseries([a+a*c, a+a*b, a+b+c]);

eq1 := a+a*c;

eq2 := a+a*b;

eq3 := a+b+c;

eq1a := Homogenize(eq1, h);

eq2a := Homogenize(eq2, h);

eq3a := Homogenize(eq3, h);

T3:=lexdeg([a,b,c,h]);

GB := Basis([eq1a,eq2a,eq3a], T3); #a

 

#MonomialHilbertPoincare(LeadingMonomial(GB[1],T3), LeadingMonomial(GB[2],T3), LeadingMonomial(GB[3],T3));

 

with(PolynomialIdeals):

MonomialHilbertPoincare := proc (I3)

#I3:=[LeadingMonomial(GB[1],T3), LeadingMonomial(GB[2],T3), LeadingMonomial(GB[3],T3)];

T2:=lexdeg([h,c,b,a]);

varj := [h,c,b,a];

I2 := InterReduce(I3, T2);

s := nops(I2);

if I2[1] = 0 then return 1 end if:

if I2[1] = 1 then return 0 end if:

if degree(I2[s]) = 1 then return (1-varj[1])^s end if:

lt := LeadingTerm(I2[s],T2);

leadexp := [degree(lt[2],h),degree(lt[2],c),degree(lt[2],b),degree(lt[2],a)];

j := 1;

for z from 1 to nops(leadexp) do

                if leadexp[j] = 0 then

                                j := j + 1;

                end if:

od:

finallist := [];

for z from 1 to nops(GB) do

                finallist := [op(finallist), GB[z]+varj[j]];

od:

quotientlist := Generators(Quotient(GB, varj[j]));

finallist2 := [];

for z from 1 to nops(quotientlist) do

                finallist2 := [op(finallist2), op(z,quotientlist)];

od:

return MonomialHilbertPoincare(finallist) + varj[1]*MonomialHilbertPoincare(finallist2);

end proc;

F:=[LeadingMonomial(GB[1],T3), LeadingMonomial(GB[2],T3), LeadingMonomial(GB[3],T3)];

MonomialHilbertPoincare(F);

 

 Do Hilbert series function classify all or only some type or some form of ideals?

 

1 2 3 4 5 Page 1 of 5