Joe Riel

7702 Reputation

22 Badges

14 years, 59 days

MaplePrimes Activity


These are Posts that have been published by Joe Riel

This isn't strictly a Maple question, however, it arises because I'm trying to convert a Maple postscript plot to a png and it is not working; the result has no background color so is essentially impossible to view.  I use ImageMagick's convert to convert from eps to png.  Previously I hadn't had a problem with that, probaby one of my upgrades has changed something (ImageMagick).  Any ideas?  Presumably there is a way to force a background color with the ImageMagick convert command, but the obvious guesses haven't worked. 

A recent post asks how to create a Maple permutation iterator, that is, a procedure that, on successive calls, iterates through each permutation of a given input.  I suggested a routine that solved the problem, however, I wasn't satisfied with it.  It was slower than it should be.  Later I suggested an improvement.  Here is another improvement.  It uses the same algorithm (algorithm L, from The Art of Computer Programming, vol. 4, fasicle 2, by Donald E. Knuth) if the input has repeated elements, but uses a different method, algorithm T, ibid., if the input consists of distinct elements.  The sequences of permutations for the two algorithms differ, the second algorithm uses the initial order for the first element and consecutive outputs differ by one transposition.

Is the MaplePrimes server clock off by about fifteen minutes?  The posted times differ by about that from what I expect.

John Fredsted suggested using the following procedure (slightly modified) to determine whether an expression was deeply algebraic.

isDeeplyAlgebraic := proc(x)
	if not type(x,'algebraic') then false
	elif type(x,'atomic') then true
	else andmap(procname,x)
	end if
end proc:
TypeTools:-AddType('DeeplyAlgebraic1'
                   , proc(x)
                         if not x :: 'algebraic' then false;
                         elif x :: 'atomic' then true;
                         else andmap(type,x,'DeeplyAlgebraic1');
                         end if;
                     end proc);

The first is a completely flat expression, the second is deeply nested.  The following graphs plot the time required to determine whether each expression is "deeply algebraic" as n increases, with each approach. The graph on the left is the time required to evaluate expr1, the graph on right is for expr2.  The red plot corresponds to the procedure, the green plot corresponds to the type. As you can see, for both flat and nested expressions, the procedure is significantly faster than the type.

 

I then did some testing to see whether the type matching could be improved.  A more efficient use of the type mechanism is to use a structured type rather than a procedure.  Alas, I don't believe that it is possible to create a purely structured type, with no use of 'satisfies', that is equivalent to what we want.  Here is the best I could come up

TypeTools:-AddType('DeeplyAlgebraic3'
                   , 'And'('algebraic'
                           , 'Or'('atomic'
                                  , 'satisfies'(x->andmap(type,x,'DeeplyAlgebraic3'))
                                 )));

Adding that to each graph gives the following two plots

 

The yellow line (p3) corresponds to this new type.  For expr1, the flat expression, it is significantly faster than the previous type, and approaches the speed of the standalone procedure.  Alas, for expr2, the nested expression, it is even slower than the previous type.  However, the reason it is slower is that with a nested expression the 'satisfies' part of the type has to be evaluated, which generates a call to a user-level procedure.

This observation suggests that if the type could be expressed as a structured type, with no use of 'satisfies', it might be significantly more efficient.  While I can see no way to do that with the desired predicate, it is possible to construct a type specific to these two examples:

TypeTools:-AddType('nestedF', 'And(algebraic,Or(atomic,function(Or(atomic,nestedF))))');

This isn't equivalent to the original predicate because it only works with functions, not operators (+, *, etc).

Here are the results with that type

Now we are making progress.  The blue plot (p4) is the time for this restricted type.  It is significantly faster than even the standalone procedure.

Note that if there were a structured type, say allops, that returned true if all of the operands of an expression match the given type, then we would be able to construct a purely structured type that matches our original predicate, that is,

TypeTools:-AddType('DeeplyAlgebraic4'
                   , 'And(algebraic
                          , Or(atomic
                               , allops(DeeplyAlgebraic4)))');

This new MaplePrimes editor is not so bad as I feared. It has some quirks, to be sure. Would it be possible to add a toggle between normal and monospace text?  That would simplify the task of writing readable Maple input code, that is, it would eliminate the need to scroll the Format box.

5 6 7 8 9 10 11 Last Page 7 of 16