sursumCorda

922 Reputation

13 Badges

2 years, 206 days

MaplePrimes Activity


These are questions asked by sursumCorda

For instance, given nine integer x1, x2, …, x9 satisfying x1, x2, …, x9 ≥ -5 and x13x23+…+x93=0, the goal is to maximize x1 + x2 + … + x9. However, according to Optimization/Options,  is not accepted by the Optimization:-Maximize command. A probable method is applying floor into the optimization variables; unfortunately, I can only get: Error, (in Optimization:-NLPSolve) no improved point could be found

(*restart;*)
vars := [x || (1 .. 9)]:
Optimization:-Maximize(`?()`(`+`, floor~(expr)), [add(floor~(expr) ^~ 3) = 0, expr[] >=~ -5], initialpoint = (unapply~(expr) =~ rand(-5 .. 10))()); # Alternatives to exhaustive search?
Error, (in Optimization:-NLPSolve) no improved point could be found

Is there any workaround to solve this problem? 

I think that the following worksheet is self-explaining: 
 

restartNULL

interface(version)

`Standard Worksheet Interface, Maple 2023.1, Windows 10, July 7 2023 Build ID 1723669`

(1)

evalf(LinearAlgebra:-MatrixFunction(`<|>`(`<,>`(1, 0, 0), `<,>`(1, 1, I), `<,>`(3, 0, 2)), 'x'/(exp('x')-1), 'x'))

Matrix(%id = 36893489913840207380)

(2)

(* Yet in many cases, the input may be inexact, for we need to speed up computations and decrease memory usage. *)

m := Matrix([[1, 1, 3], [0, 1, 0], [0, I, 2]], datatype = complex(sfloat)):
Digits := 10:
do
    print(CodeTools:-Usage(LinearAlgebra:-MatrixFunction(m, 'x'/(exp('x') - 1), 'x'), quiet), Digits++)
until Digits > 20:

Matrix(3, 3, {(1, 1) = .5819767069, (1, 2) = -.3333333333+.1931757357*I, (1, 3) = -.8068242642, (2, 1) = 0., (2, 2) = .5819767069, (2, 3) = 0., (3, 1) = 0., (3, 2) = -.2689414214*I, (3, 3) = .3130352855}), 10

 

Matrix(3, 3, {(1, 1) = .5819767069, (1, 2) = -.33333333332+.19317573586*I, (1, 3) = -.8068242642, (2, 1) = 0., (2, 2) = .5819767069, (2, 3) = 0., (3, 1) = 0., (3, 2) = -.2689414214*I, (3, 3) = .3130352855}), 11

 

Matrix(3, 3, {(1, 1) = .5819767069, (1, 2) = -.333333333321+.193175735853*I, (1, 3) = -.8068242642, (2, 1) = 0., (2, 2) = .5819767069, (2, 3) = 0., (3, 1) = 0., (3, 2) = -.2689414214*I, (3, 3) = .3130352855}), 12

 

Matrix(3, 3, {(1, 1) = .5819767069, (1, 2) = -.3333333333209+.1931757358526*I, (1, 3) = -.8068242642, (2, 1) = 0., (2, 2) = .5819767069, (2, 3) = 0., (3, 1) = 0., (3, 2) = -.2689414214*I, (3, 3) = .3130352855}), 13

 

Matrix(3, 3, {(1, 1) = .5819767069, (1, 2) = -.33333333332087+.19317573585263*I, (1, 3) = -.8068242642, (2, 1) = 0., (2, 2) = .5819767069, (2, 3) = 0., (3, 1) = 0., (3, 2) = -.2689414214*I, (3, 3) = .3130352855}), 14

 

Matrix(3, 3, {(1, 1) = .5819767069, (1, 2) = -.333333333320870+.193175735852624*I, (1, 3) = -.8068242642, (2, 1) = 0., (2, 2) = .5819767069, (2, 3) = 0., (3, 1) = 0., (3, 2) = -.2689414214*I, (3, 3) = .3130352855}), 15

 

Matrix(3, 3, {(1, 1) = .5819767068693265, (1, 2) = .9999999999999999-3.806824264*I, (1, 3) = -.8068242641099854, (2, 1) = 0., (2, 2) = .5819767068693265, (2, 3) = 0., (3, 1) = 0., (3, 2) = -.2689414214*I, (3, 3) = .3130352854993314}), 16

 

Matrix(3, 3, {(1, 1) = .58197670686932644, (1, 2) = .99999999999999997-3.806824264*I, (1, 3) = -.80682426410998598, (2, 1) = 0., (2, 2) = .58197670686932644, (2, 3) = 0., (3, 1) = 0., (3, 2) = -.2689414214*I, (3, 3) = .31303528549933112}), 17

 

Matrix(3, 3, {(1, 1) = .581976706869326423, (1, 2) = -.999999999999999997+2.19317573589001464*I, (1, 3) = -.806824264109985348, (2, 1) = 0., (2, 2) = .581976706869326423, (2, 3) = 0., (3, 1) = 0., (3, 2) = -.2689414214*I, (3, 3) = .313035285499331308}), 18

 

Matrix(3, 3, {(1, 1) = .5819767068693264245, (1, 2) = -.2500000000000000000-0.5682426411e-1*I, (1, 3) = -.8068242641099853627, (2, 1) = 0., (2, 2) = .5819767068693264245, (2, 3) = 0., (3, 1) = 0., (3, 2) = -.2689414214*I, (3, 3) = .3130352854993313037}), 19

 

Matrix(%id = 36893489913905117652), 20

(3)

# Is `linalg:-matfunc` better than `LinearAlgebra:-MatrixFunction`?!
Digits := 10:
linalg:-matfunc(m, 'x'/(exp('x') - 1), 'x');

Matrix(3, 3, {(1, 1) = .5819767070, (1, 2) = -.3386968877+.2092663986*I, (1, 3) = -.8068242645, (2, 1) = 0., (2, 2) = .5819767070, (2, 3) = 0., (3, 1) = 0., (3, 2) = -.2689414215*I, (3, 3) = .3130352855})

(4)

(*
Even for a 3×3 matrix, the number of digits has to be set to 20.
So … how can you certify that the following output is validated?
*)
_seed := 1234:

LinearAlgebra:-MatrixFunction(LinearAlgebra:-RandomMatrix(50, density = .5, generator = -2*Pi .. 2*Pi, datatype = complex[8]), 'x'/(exp('x')-1), 'x')

Warning, the use of _seed is deprecated.  Please consider using one of the alternatives listed on the _seed help page.

 

Matrix(%id = 36893490216779135924)

(5)


 

Download funm.mws

How do you confirm the validity of the last output? 

> op(3, eval(LinearAlgebra:-MatrixFunction));
 = 
  Copyright (c) 2002 Waterloo Maple Inc. All rights reserved.

And does this mean that LinearAlgebra['MatrixFunction'] is so out-dated that the return value is less effective in certain cases?

Wolfram's marketing literature states that a compiled function may generate the dates for the years 1 through 5.7 million in a couple of seconds rather than in minutes (comparing to the "uncompiled implementation").
The given function in this link can be translated into Maple language as follows: 

(*
  Note that this is only a mathematical program that outputs some data,
   hence 'Easter(-2, 1)' will never return real Gregorian Easter dates!
*)
Easter:=proc(BEGIN::integer[4],END::integer[4],$)::Array(BEGIN..END,[integer[1..12],integer[1..31]]);# the parent function
	description "https://www.wolfram.com/language/12/code-compilation/compute-the-date-of-easter.html";
	local computus::procedure[[integer[1 .. 12], integer[1 .. 31]]](integer):=proc(Year::integer,` $`)::[integer[1..12],integer[1..31]];# the child function
		options threadsafe;
		local a::nonnegint,b::integer,c::nonnegint,d::integer,e::nonnegint,f::integer,g::nonnegint,h::nonnegint,i::nonnegint,j::nonnegint,k::nonnegint,Month::integer[1..12],Day::integer[1..31];
		(* For compatibility, when `Year` is nonpositive, the command `iquo` must be replaced with slower `floor`. *)
		if Year<=0 then
			a,b,c:=Year mod 19,floor(Year/100),Year mod 100;
			d,e,f:=floor(b/4),b mod 4,floor((8*b+13)/25);
			g,h,i:=19*a+b-d-f+15 mod 30,floor(c/4),c mod 4;
			j:=floor((a+11*g)/319);k:=2*e+2*h-i-g+j+32 mod 7;
			Month:=floor((g-j+k+90)/25);Day:=g-j+k+Month+19 mod 32
		else
			a,b,c:=irem(Year,19),iquo(Year,100),irem(Year,100):
			d,e,f:=iquo(b,4),irem(b,4),iquo(8*b+13,25);
			g,h,i:=irem(19*a+b-d-f+15,30),iquo(c,4),irem(c,4);
			j:=iquo(a+11*g,319);k:=irem(2*e+2*h-i-g+j+32,7);
			Month:=iquo(g-j+k+90,25);Day:=irem(g-j+k+Month+19,32)
		fi;
		[Month,Day]
	end;
	Array(BEGIN..END,computus)
end:

However, as "no nested procedures can be translated" to optimized native machine code (cf. ), executing Easter(1, 5700000) has to take at least two minutes

Is there some workaround that can provide improved performance for such a numerical procedure that contains a nested procedure? In other words, is it possible to produce the `result` (without modifying the algorithm) in two seconds in modern Maple as that Wolfram marketing literature claims?

The old question "Longest distance in a graph via Maple code" offers some general methods to find longest paths in a given graph, while for directed acyclic graphs, the longest paths can be found much more directly via built-in functions. However, it apprears that even for small dags, Maple cannot solve this in an acceptable time. In the following example, I'd like to count the number of nodes that on longest paths for certain source and target vertexes.
 

restart;

_seed := 1234

Warning, the use of _seed is deprecated.  Please consider using one of the alternatives listed on the _seed help page.

 

G := GraphTheory:-RandomGraphs:-RandomNetwork(200, .2, 'acyclic', 'weights' = 0. .. 2)

G__0 := applyop(`-`, -1, G)``

GRAPHLN(directed, weighted, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200], Array(1..200, {(1) = {2, 3, 4}, (2) = {5}, (3) = {4, 5}, (4) = {5}, (5) = {6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18}, (6) = {11, 12, 13, 14, 15, 17, 18, 19, 21}, (7) = {9, 10, 11, 16, 17, 20, 22}, (8) = {12, 14, 16, 17, 19, 20, 21, 22, 23}, (9) = {11, 14, 21, 23}, (10) = {11, 13, 18, 19, 20, 21, 23}, (11) = {14, 15, 16, 17, 18, 21, 23}, (12) = {13, 15, 18, 19, 20, 22}, (13) = {14, 15, 16, 17, 21}, (14) = {19, 20, 22}, (15) = {19, 20, 22, 23}, (16) = {17, 18, 21}, (17) = {19, 20, 23}, (18) = {19, 20, 21}, (19) = {20, 24, 25}, (20) = {22, 23, 25}, (21) = {23, 24, 25}, (22) = {23, 24, 25}, (23) = {24, 25}, (24) = {26, 27, 29}, (25) = {27, 28, 29}, (26) = {28, 29, 30}, (27) = {28, 29, 31, 32, 33}, (28) = {32, 33}, (29) = {32, 33}, (30) = {34, 35, 38, 39}, (31) = {32, 37, 38, 39}, (32) = {33, 36, 37, 38}, (33) = {35, 36, 39}, (34) = {36, 38, 39}, (35) = {37, 39}, (36) = {37, 39}, (37) = {39, 40}, (38) = {39, 40}, (39) = {40}, (40) = {41, 42}, (41) = {43, 44, 47, 48, 49}, (42) = {44, 45, 46, 47, 48, 49}, (43) = {47, 49, 50, 55, 56, 57}, (44) = {45, 48, 50, 51, 52, 53, 54, 56}, (45) = {46, 47, 49, 50, 52, 56}, (46) = {47, 48, 49, 50, 51, 52, 53, 56, 57}, (47) = {49, 50, 51, 52, 54, 56, 57}, (48) = {49, 51, 52, 53, 54, 55, 56, 57}, (49) = {50, 52, 53, 54, 57}, (50) = {51, 57}, (51) = {53, 54, 57}, (52) = {53, 55, 57}, (53) = {54, 56}, (54) = {56, 58}, (55) = {58}, (56) = {58}, (57) = {58}, (58) = {59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75}, (59) = {60, 61, 66, 68, 70, 71, 74, 75, 76, 77}, (60) = {61, 63, 67, 68, 70, 72, 73, 77}, (61) = {62, 66, 69, 70, 71, 72, 73, 75, 76, 77}, (62) = {65, 68, 75, 76, 77}, (63) = {65, 66, 69, 70, 72, 73, 76, 77}, (64) = {65, 67, 68, 69, 70, 71, 73, 77}, (65) = {66, 70, 72, 73, 74, 76}, (66) = {68, 70, 71, 72, 73, 74, 75, 76, 77}, (67) = {69, 70, 71, 74, 76}, (68) = {73, 74}, (69) = {71, 76, 77}, (70) = {71, 73, 77}, (71) = {72, 76, 77}, (72) = {75}, (73) = {75, 76}, (74) = {76}, (75) = {76}, (76) = {77, 78, 79, 80, 81, 82, 83, 85, 86}, (77) = {79, 80, 82, 84, 85}, (78) = {79, 83, 85, 87}, (79) = {81, 82, 83, 85, 86, 87}, (80) = {83, 86}, (81) = {83, 84, 87}, (82) = {87}, (83) = {85, 86, 87}, (84) = {85, 87}, (85) = {87}, (86) = {87}, (87) = {88, 89}, (88) = {90, 91, 92, 93, 94}, (89) = {90, 91, 93, 94, 95}, (90) = {96, 97, 99, 101, 103, 104, 107, 108, 109, 110, 112, 115, 117, 118, 120}, (91) = {92, 94, 96, 97, 98, 100, 101, 102, 105, 106, 107, 110, 113, 116, 117, 118, 120}, (92) = {95, 97, 98, 99, 101, 103, 106, 107, 108, 111, 112, 113, 115, 117, 119, 120}, (93) = {95, 96, 98, 100, 104, 106, 109, 111, 112, 113, 116, 118, 119, 120}, (94) = {95, 99, 100, 102, 103, 104, 106, 108, 109, 110, 111, 112, 113, 114, 115, 117, 118, 119, 120}, (95) = {97, 98, 99, 100, 102, 103, 104, 105, 107, 108, 109, 111, 112, 113, 114, 115, 116, 117, 118, 120}, (96) = {98, 100, 102, 103, 104, 106, 107, 110, 111, 114, 119, 120, 121}, (97) = {99, 100, 102, 104, 106, 107, 108, 109, 111, 114, 118, 119}, (98) = {102, 103, 107, 110, 111, 112, 113, 114, 116, 117, 119, 120, 121}, (99) = {101, 102, 104, 106, 107, 112, 117, 120}, (100) = {101, 104, 105, 106, 109, 110, 116, 117, 119, 120, 121}, (101) = {102, 105, 109, 110, 111, 112, 113, 114, 115, 117, 118, 119, 120}, (102) = {103, 106, 107, 108, 110, 112, 113, 114, 117, 118, 119}, (103) = {104, 105, 107, 108, 109, 110, 111, 113, 115, 116, 119, 120, 121}, (104) = {105, 106, 109, 110, 114, 115, 116, 118, 119}, (105) = {106, 108, 109, 110, 113, 114, 116, 117}, (106) = {107, 108, 109, 112, 114, 117, 118, 119, 121}, (107) = {110, 114, 116, 119, 120}, (108) = {111, 112, 113, 114, 118, 119, 120, 121}, (109) = {113, 116, 117, 118, 121}, (110) = {111, 113, 117, 119, 120, 121}, (111) = {112, 113, 115, 118, 120}, (112) = {113, 114, 116, 117, 118, 119, 120}, (113) = {116, 117, 119, 121}, (114) = {115, 116, 117, 121}, (115) = {116, 120}, (116) = {119, 121}, (117) = {118, 119, 121}, (118) = {121}, (119) = {121}, (120) = {121}, (121) = {122, 123, 124, 125, 126}, (122) = {123, 124, 125, 126, 127}, (123) = {126}, (124) = {126, 127}, (125) = {127}, (126) = {127}, (127) = {128, 129}, (128) = {130}, (129) = {130}, (130) = {131, 132}, (131) = {132, 133, 135}, (132) = {134, 135}, (133) = {134, 136, 137, 138, 140, 141, 142}, (134) = {135, 136, 139, 140, 141}, (135) = {136, 137, 139, 140, 141, 142}, (136) = {145, 146, 147}, (137) = {139, 141, 143, 145, 147, 148}, (138) = {139, 140, 143, 144, 145, 148}, (139) = {141, 143, 145}, (140) = {143, 145, 146, 147, 148}, (141) = {142, 144, 145, 146, 147}, (142) = {143, 144, 146, 148}, (143) = {145, 146, 147, 148}, (144) = {146, 149}, (145) = {147}, (146) = {149}, (147) = {149}, (148) = {149}, (149) = {150, 151, 152, 153, 154, 155, 156, 157, 158}, (150) = {152, 153, 155, 157, 158}, (151) = {152, 153, 159}, (152) = {154, 158}, (153) = {154, 155, 156}, (154) = {156, 158, 159}, (155) = {158}, (156) = {157, 158, 159}, (157) = {158}, (158) = {159}, (159) = {160, 161, 162, 163}, (160) = {161, 163, 166, 167}, (161) = {165, 166, 167}, (162) = {163, 165}, (163) = {164, 166, 167}, (164) = {166}, (165) = {166, 168, 169}, (166) = {169}, (167) = {168}, (168) = {169, 170, 171, 172, 173, 174, 177, 178, 179, 180, 182}, (169) = {170, 171, 172, 173, 174, 175, 176, 177, 178, 180, 181, 182}, (170) = {172, 173, 174, 175, 176, 180, 182, 183, 185}, (171) = {172, 174, 176, 177, 181, 182, 185}, (172) = {175, 176, 177, 183, 185}, (173) = {175, 176, 178, 183, 185}, (174) = {175, 180, 181, 183, 184, 185}, (175) = {181, 182, 183, 185}, (176) = {177, 178, 179, 182}, (177) = {178, 179, 184, 185}, (178) = {179, 180, 182, 183, 184}, (179) = {180, 182, 185}, (180) = {181, 182}, (181) = {184}, (182) = {185}, (183) = {187, 188, 190}, (184) = {187, 188, 189}, (185) = {186, 188, 190}, (186) = {187, 188, 190, 191, 193, 194, 196}, (187) = {188, 190, 192, 193, 194, 195}, (188) = {189, 190, 191, 192, 194}, (189) = {190, 191, 196}, (190) = {191, 192, 195, 196}, (191) = {193, 196, 199}, (192) = {194, 196, 198, 199}, (193) = {197, 199}, (194) = {195, 196, 197}, (195) = {196, 198, 199}, (196) = {198, 199}, (197) = {198}, (198) = {199, 200}, (199) = {200}, (200) = {}}), `GRAPHLN/table/1`, )

(1)

t, s := combinat:-randcomb(GraphTheory:-Vertices(G__0), 5^2), combinat:-randcomb(GraphTheory:-Vertices(G__0), integermul2exp(5, 2))

[12, 13, 22, 23, 41, 65, 70, 80, 88, 97, 105, 119, 124, 127, 129, 132, 135, 138, 146, 150, 165, 170, 189, 193, 199], [6, 13, 28, 29, 31, 41, 42, 49, 55, 85, 98, 104, 136, 141, 162, 166, 167, 168, 192, 199]

(2)

"DataFrame((`M__1`:=CodeTools:-Usage(Matrix(numelems(s),numelems(t),(i,j)->numelems((GraphTheory:-BellmanFordAlgorithm(`G__0`,s[i],t[j]))[1]),datatype=integer[2]))),'columns'=t,'rows'=s)"

memory used=7.99GiB, alloc change=0 bytes, cpu time=5.74m, real time=5.63m, gc time=22.55s

 

module DataFrame () description "two-dimensional rich data container"; local columns, rows, data, binder; option object(BaseDataObject); end module

(3)

"DataFrame((`M__2`:=CodeTools:-Usage(Matrix(numelems(s),numelems(t),proc(i::posint,j::posint,` $`)::nonnegint;  uses ListTools,GraphTheory; local ts::list(posint):=TopologicSort(`G__0`,'output'='permutation'),q::posint:=Search(t[j],ts),p::posint:=Search(s[i],ts); if  p>q then 0 elif q=p then 1 else numelems(BellmanFordAlgorithm(`G__0`,s[i],t[j])[1]) fi end,datatype=integer))),':-columns'=t,':-rows'=s)"

memory used=4.34GiB, alloc change=32.00MiB, cpu time=3.26m, real time=3.19m, gc time=14.34s

 

module DataFrame () description "two-dimensional rich data container"; local columns, rows, data, binder; option object(BaseDataObject); end module

(4)

EqualEntries(M__ || (1 .. 2))

true

(5)

 


 

Download longest_paths_in_a_DAG.mw

Unfortunately, I have to wait for almost four minutes in the above instance. Can this task be done in 0.4s?

GraphTheory:-GraphEqual says that G1 and G2 are equal, but GraphTheory:-AllPairsDistance gives different results instead: 

restart;

with(GraphTheory)

M := `<|>`(`<,>`(0, 0, 0), `<,>`(1, 0, 0), `<,>`(1, 1, 0))

G__1 := Graph(convert(-M, Matrix, datatype = integer[8]))

G__2 := Graph(convert(-M, Matrix, datatype = integer))

GraphEqual(G__1, G__2)

true

(1)

AllPairsDistance(G__1)

AllPairsDistance(G__2)

Matrix(%id = 36893491227039185244)

 

Error, (in GraphTheory:-AllPairsDistanceExt) negative cycle detected

 

 

Download allpairs.mw

So, which one is incorrect? Any reasons?

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