@Christopher2222 I gave it a brief whirl last night, and did not succeed with Maple 14. The StringTools package's user-accessible routines utilize a technique where a compiled external function (in a shared library, aka dll on MS-Windows) replaces a Library stub function upon first invocation. Even the Library part of the code is not easy to figure out completly, in the Maple debugger. I believe that some or all StringTools routines have their complete body implemented using Maple's OpenMaple API, and are compiled and thus not visible for examination. (This is one reason why the package is so very fast.) The error message that you cite gets issued when a call_external is made. The argument `ospd3` passes initial Library procedure checks, but appears to fall afoul of another check which may be in a compiled external function. It might not be possible to circumvent.

@Axel Vogt Greatstuff.

I suspect that xg and wg can be pulled out of Legendre16 (and even out of L), and passed in as arguments. And K's formula could probably be burned-in or otherwise inlined into Legendre16 (which could take x and s as 2 first args, instead of f). It looks like Legendre16 could thus become not only fully evalhf'able but also Compile'able and/or fullly exportable via CodeGeneration[C].

...which reminds me of something else.

@Christopher2222 Reading a file into memory will be much more efficient than scanning it, repeatedly, as a file. Repeated file i/o is extremely inefficient.

But there are other questions of efficiency about tasks likes this which are interesting. A great deal of the work for this and related tasks are checks on membership and position. Like use of `member` or a set of strings in Maple, say.

Ask a nine year-old to look up a given word in the dictionary. She won't start on the first page and then check every word on the page, from top to bottom, and then repeat all that on page 2, etc, etc. No, instead she'll crack the whole dictionary book at about the 3/4 mark, and then compare the top corner with the first letter of the given lookup-word. And then she'll continue seaching cleverly, and get to the right page in a dozen seconds or so.

And that is all possible because the words in dictionary are sorted usefully. If I had a dictionary which was not known to be ordered "alphabetically" then looking up words would be much less efficient.

In Maple 8, a set in Maple had its members ordered by memory address. In Maple 12 and later, a set's members are ordered according to the value of kernelopts(setsort). And the ordering of members of a set is now done according to some rules which are quite different from mere memory address. There are a few different schemes (for different setsort values), but the chosen scheme is unchanging for any Maple kernel session. And the new schemes are largely based upon lexicographic ordering. In particular, strings in a set are now sorted in such a way that knowledge of the current setsort value could allow for more efficient membership testing of any set comprised of only strings.

The StringTools package was written before set ordering changed from being memory-address-based to being setsort-(lexicographically)-based. And unlike Matrices, say, a Maple set does not have a `datatype`. So there is no super-cheap test which indicates that a given set can only contain strings. It therefore seems doubtful that StringTools makes use of modern Maple's set ordering in order to do more efficient searches and membership tests for user-supplied sets. It's possible that it might have been updated to take advantage of setsort ordrering when operating within its internal routines on temporary sets that it constructs itself during a computation.

On the other hand, equivalent computations have longer been technically possible in Maple. A string can be converted to a Vector of hardware integers. The first entry can be used to contain the length. Programs which compare, or test for membership in large collections of such representations of words, can be compiled and made very efficient.

Running the commandline interface of Maple 15, on Unix,

% maple15 --setsort=1

> {"a","s","h","M","b","C"}; kernelopts(setsort);

                        {"C", "M", "a", "b", "h", "s"}

                                       1

> quit

% maple15 --setsort=2

> {"a","s","h","M","b","C"}; kernelopts(setsort);

                        {"s", "h", "b", "a", "M", "C"}

                                       2

I don't know whether modern Maple's StringTools relies on such orderings, when present, to do faster lookups.

@Christopher2222 Reading a file into memory will be much more efficient than scanning it, repeatedly, as a file. Repeated file i/o is extremely inefficient.

But there are other questions of efficiency about tasks likes this which are interesting. A great deal of the work for this and related tasks are checks on membership and position. Like use of `member` or a set of strings in Maple, say.

Ask a nine year-old to look up a given word in the dictionary. She won't start on the first page and then check every word on the page, from top to bottom, and then repeat all that on page 2, etc, etc. No, instead she'll crack the whole dictionary book at about the 3/4 mark, and then compare the top corner with the first letter of the given lookup-word. And then she'll continue seaching cleverly, and get to the right page in a dozen seconds or so.

And that is all possible because the words in dictionary are sorted usefully. If I had a dictionary which was not known to be ordered "alphabetically" then looking up words would be much less efficient.

In Maple 8, a set in Maple had its members ordered by memory address. In Maple 12 and later, a set's members are ordered according to the value of kernelopts(setsort). And the ordering of members of a set is now done according to some rules which are quite different from mere memory address. There are a few different schemes (for different setsort values), but the chosen scheme is unchanging for any Maple kernel session. And the new schemes are largely based upon lexicographic ordering. In particular, strings in a set are now sorted in such a way that knowledge of the current setsort value could allow for more efficient membership testing of any set comprised of only strings.

The StringTools package was written before set ordering changed from being memory-address-based to being setsort-(lexicographically)-based. And unlike Matrices, say, a Maple set does not have a `datatype`. So there is no super-cheap test which indicates that a given set can only contain strings. It therefore seems doubtful that StringTools makes use of modern Maple's set ordering in order to do more efficient searches and membership tests for user-supplied sets. It's possible that it might have been updated to take advantage of setsort ordrering when operating within its internal routines on temporary sets that it constructs itself during a computation.

On the other hand, equivalent computations have longer been technically possible in Maple. A string can be converted to a Vector of hardware integers. The first entry can be used to contain the length. Programs which compare, or test for membership in large collections of such representations of words, can be compiled and made very efficient.

Running the commandline interface of Maple 15, on Unix,

% maple15 --setsort=1

> {"a","s","h","M","b","C"}; kernelopts(setsort);

                        {"C", "M", "a", "b", "h", "s"}

                                       1

> quit

% maple15 --setsort=2

> {"a","s","h","M","b","C"}; kernelopts(setsort);

                        {"s", "h", "b", "a", "M", "C"}

                                       2

I don't know whether modern Maple's StringTools relies on such orderings, when present, to do faster lookups.

@Christopher2222 I considered that case but figured that the original post was slightly ambiguous on the issue and (much more importantly) that if I has misinterpreted then it didn't matter since a pre-check would be so trivial that anyone could write it.

@Christopher2222 I considered that case but figured that the original post was slightly ambiguous on the issue and (much more importantly) that if I has misinterpreted then it didn't matter since a pre-check would be so trivial that anyone could write it.

@Christopher2222 Sorry, when turning the code into a procedure I inadvertantly left the Search to be hard-coded for the letter "r". The Search line ought to be,

    pos:=Search(char,input);

So the procedure would be,

restart:

with(StringTools):
with(PatternDictionary):

bid:= Create(`builtin`):
words:= [seq](Get(bid,i),i=1..Size(bid)-1):

unwith(PatternDictionary):
unwith(StringTools):

findall:=proc(input::string,char::string,lo::posint,hi::posint)
global words;
local i, all, pos, final;
uses StringTools;
   if length(char)<>1 then
      error "expecting single character for 2nd argument";
   end if;
   if hi>length(input) then
      error "expecting 4th argument to be posint at most the length of 1st argument";
   end if;
   all:=Explode(input);
   pos:=Search(char,input);
   if pos>0 then
      all := [all[1..pos-1][],all[pos+1..-1][]];
   end if;
   for i from lo to hi do
      final[i]:=seq(Anagrams(Implode([x[],char]),words),
                    x in {combinat:-choose(all,i-1)[]});
   end do;
   eval(final);
end proc:

findall("speak","s",5,5);

                                table([5 = "speak"])

findall("speak","s",3,5);

         table([3 = ("sea", "ask", "spa", "sap"), 4 = ("sake", "apse"), 5 = "speak"])

@Christopher2222 Sorry, when turning the code into a procedure I inadvertantly left the Search to be hard-coded for the letter "r". The Search line ought to be,

    pos:=Search(char,input);

So the procedure would be,

restart:

with(StringTools):
with(PatternDictionary):

bid:= Create(`builtin`):
words:= [seq](Get(bid,i),i=1..Size(bid)-1):

unwith(PatternDictionary):
unwith(StringTools):

findall:=proc(input::string,char::string,lo::posint,hi::posint)
global words;
local i, all, pos, final;
uses StringTools;
   if length(char)<>1 then
      error "expecting single character for 2nd argument";
   end if;
   if hi>length(input) then
      error "expecting 4th argument to be posint at most the length of 1st argument";
   end if;
   all:=Explode(input);
   pos:=Search(char,input);
   if pos>0 then
      all := [all[1..pos-1][],all[pos+1..-1][]];
   end if;
   for i from lo to hi do
      final[i]:=seq(Anagrams(Implode([x[],char]),words),
                    x in {combinat:-choose(all,i-1)[]});
   end do;
   eval(final);
end proc:

findall("speak","s",5,5);

                                table([5 = "speak"])

findall("speak","s",3,5);

         table([3 = ("sea", "ask", "spa", "sap"), 4 = ("sake", "apse"), 5 = "speak"])

@Christopher2222 That's a Unix file location. No such example will work on every operating system. Some OS might have a system dictionary in one place, and another might not even have one at all.

And it's not a "dictionary" file in the sense of having definitions. It's just a word list, I think. One word per line. ASCII.

Why did I not see this before? Perhaps I shouldn't have been so quick to believe the claim attributed to your instructor.

Note that I changed the initial assignment of various variables to be exact rationals instead of floats, and removed the `evalf` around a fraction of Pi. See the EKM_04.mw upload link, for that in the preliminaries.

> simpleK :=map(expand(K)):

> Digits := 500:

> Nsols := [fsolve(Determinant(simpleK), N)]:

> K8 := eval(simpleK, N = Nsols[8]):

> X8 := Matrix([NullSpace(evalf(K8))[]]):

> Norm(K8.X8);

                                  -476
                         3.7677 10    

> for i to nops(Nsols) do
>    KK[i] := eval(simpleK, N = Nsols[i]);
>    NS[i] := NullSpace(evalf(K8));
>    if nops(NS[i]) > 0 then
>       try XX[i] := Matrix([NullSpace(evalf(KK[i]))[]]);
>          print([i, Norm(KK[i].XX[i]), evalf[10](Norm(XX[i]))]);
>       catch:
>       end try;
>    end if;
> end do;

                [            -474              ]
                [1, 2.5289 10    , 0.7880837989]
                [            -474              ]
                [2, 2.5753 10    , 0.7766997177]
                [            -474              ]
                [3, 2.4118 10    , 0.7576109811]
                [           -476              ]
                [4, 4.755 10    , 0.7312073739]
                [            -475              ]
                [5, 1.5963 10    , 0.7150784196]
                [           -476              ]
                [7, 3.160 10    , 0.7848194670]
                [            -476              ]
                [8, 3.8677 10    , 0.8215593884]
               [             -476              ]
               [9, 5.16758 10    , 0.8558701527]
               [              -477              ]
               [10, 4.17199 10    , 0.8847592280]
               [             -477              ]
               [11, 5.7069 10    , 0.9068848065]
               [             -477              ]
               [12, 1.0583 10    , 0.9222282989]
                [           -476              ]
                [14, 7.90 10    , 0.9460877743]
                [            -474              ]
                [15, 6.603 10    , 0.9553751693]
                [            -474              ]
                [16, 2.416 10    , 0.9599030240]
                 [          -470              ]
                 [17, 5.0 10    , 0.9980170575]
                [            -466              ]
                [18, 6.468 10    , 0.7524713989]

So I don't see what is unacceptable about these results, where each pair KK[i] and (non-zero) XX[i] is the solution given by N=Nsols[i], for i=1..18. It looks more accurate, is simpler and faster, and produces all solutions.

The (less accurate) single solution Xsol from the eigen-solving approach above matches (up to a minus sign) the more accurate result for the 8th root of the determinant of the expanded Matrix K.

> Norm(map(fnormal, XX[8]+Xsol, 10, 0.1e-79));

                                     -72
                       1.351806574 10   

Why did I not see this before? Perhaps I shouldn't have been so quick to believe the claim attributed to your instructor.

Note that I changed the initial assignment of various variables to be exact rationals instead of floats, and removed the `evalf` around a fraction of Pi. See the EKM_04.mw upload link, for that in the preliminaries.

> simpleK :=map(expand(K)):

> Digits := 500:

> Nsols := [fsolve(Determinant(simpleK), N)]:

> K8 := eval(simpleK, N = Nsols[8]):

> X8 := Matrix([NullSpace(evalf(K8))[]]):

> Norm(K8.X8);

                                  -476
                         3.7677 10    

> for i to nops(Nsols) do
>    KK[i] := eval(simpleK, N = Nsols[i]);
>    NS[i] := NullSpace(evalf(K8));
>    if nops(NS[i]) > 0 then
>       try XX[i] := Matrix([NullSpace(evalf(KK[i]))[]]);
>          print([i, Norm(KK[i].XX[i]), evalf[10](Norm(XX[i]))]);
>       catch:
>       end try;
>    end if;
> end do;

                [            -474              ]
                [1, 2.5289 10    , 0.7880837989]
                [            -474              ]
                [2, 2.5753 10    , 0.7766997177]
                [            -474              ]
                [3, 2.4118 10    , 0.7576109811]
                [           -476              ]
                [4, 4.755 10    , 0.7312073739]
                [            -475              ]
                [5, 1.5963 10    , 0.7150784196]
                [           -476              ]
                [7, 3.160 10    , 0.7848194670]
                [            -476              ]
                [8, 3.8677 10    , 0.8215593884]
               [             -476              ]
               [9, 5.16758 10    , 0.8558701527]
               [              -477              ]
               [10, 4.17199 10    , 0.8847592280]
               [             -477              ]
               [11, 5.7069 10    , 0.9068848065]
               [             -477              ]
               [12, 1.0583 10    , 0.9222282989]
                [           -476              ]
                [14, 7.90 10    , 0.9460877743]
                [            -474              ]
                [15, 6.603 10    , 0.9553751693]
                [            -474              ]
                [16, 2.416 10    , 0.9599030240]
                 [          -470              ]
                 [17, 5.0 10    , 0.9980170575]
                [            -466              ]
                [18, 6.468 10    , 0.7524713989]

So I don't see what is unacceptable about these results, where each pair KK[i] and (non-zero) XX[i] is the solution given by N=Nsols[i], for i=1..18. It looks more accurate, is simpler and faster, and produces all solutions.

The (less accurate) single solution Xsol from the eigen-solving approach above matches (up to a minus sign) the more accurate result for the 8th root of the determinant of the expanded Matrix K.

> Norm(map(fnormal, XX[8]+Xsol, 10, 0.1e-79));

                                     -72
                       1.351806574 10   

You could try this, producing a "best" eigenvalue of about 10^(1-69) and a result K.X whose norm is of the same order.

EKM_04.mw

I'm not completely convinced that this is producing the globally smallest absolute eigenvalue. And I'm not completely convinced that the smallest absolute eigenvalues tends to zero as Digits gets higher.

Also, there is probably a better way. Certainly it should not be necessary to compute all eigenvalues and their eigenvectors just to find the eigenspace of some eigenvalue closest to zero.

And minimizing the absolute values may just not be best too, since that is often not a great way to do what is (here, essentially) a rootfinding exercise. It turns what might be an easier rootfinding exercise into a global mimization exercise.

I didn't even look at the prelimiary computations, to see what it does and try and figure out whether there is some altogether different approach.

acer

You could try this, producing a "best" eigenvalue of about 10^(1-69) and a result K.X whose norm is of the same order.

EKM_04.mw

I'm not completely convinced that this is producing the globally smallest absolute eigenvalue. And I'm not completely convinced that the smallest absolute eigenvalues tends to zero as Digits gets higher.

Also, there is probably a better way. Certainly it should not be necessary to compute all eigenvalues and their eigenvectors just to find the eigenspace of some eigenvalue closest to zero.

And minimizing the absolute values may just not be best too, since that is often not a great way to do what is (here, essentially) a rootfinding exercise. It turns what might be an easier rootfinding exercise into a global mimization exercise.

I didn't even look at the prelimiary computations, to see what it does and try and figure out whether there is some altogether different approach.

acer

I wonder if there is any decent way to get a useful approximation of Variance(data2), without having to compute the solution data2.

acer

I wonder if there is any decent way to get a useful approximation of Variance(data2), without having to compute the solution data2.

acer