Advanced Search

Question: seq slower than proc

Question:seq slower than proc

Harry Garst 234 Maple 2020
performance programming linear-algebra seq determinant
May 22 2023
1

I learned about Dodgson calculation of the determinant only recently (https://en.m.wikipedia.org/wiki/Dodgson_condensation).
I am only interested in symbolic expressions of the determinant.
Furthermore, I compared several methods. Not surprisingly, the build in method is the fastest. But why is the seq method slower than the proc method for the Dodgson method? Is there anything I could do to program it more efficiently?
 

> 

restart; with(LinearAlgebra)
> 

with(combinat); with(GroupTheory)
> 

DetDef := proc (A) local i, n, sigma; description "Jeremy Johnson. Downloaded from https://www.cs.drexel.edu/~jjohnson/2016-17/winter/cs300/lectures/determinant.mw"; n := RowDimension(A); add(PermParity(Perm(sigma))*mul(A[i, sigma[i]], i = 1 .. n), `in`(sigma, permute([`$`(1 .. n)]))) end proc
> 

InnerMatrix := proc (M::Matrix) SubMatrix(M, 2 .. RowDimension(M)-1, 2 .. ColumnDimension(M)-1) end proc
> 

MatrixDet := proc (M::Matrix) local C, n, i, j; n := RowDimension(M)-1; C := Matrix(n, n); seq(seq(assign('C[i, j]', Determinant(M([i, i+1], [j, j+1]))), j = 1 .. n), i = 1 .. n); return C end proc
> 

Dodgson := proc(M::Matrix)
 MatrixDet(M);
InnerMatrix(M) ^~ (-1) *~ MatrixDet(MatrixDet(M));
do if 1 < RowDimension(%) then InnerMatrix(`%%`) ^~ (-1) *~ MatrixDet(%);
end if;
until RowDimension(%) = 1;
Trace(%):
end proc:
> 

Dodgsonseq := proc (E::Matrix) local w, dim, Z; dim := RowDimension(E); Z[dim] := E; Z[dim-1] := MatrixDet(E); Z[dim-2] := `~`[`*`](`~`[`^`](InnerMatrix(E), -1), MatrixDet(MatrixDet(E))); seq(assign('Z[w-1]', `~`[`*`](`~`[`^`](InnerMatrix(Z[w+1]), -1), MatrixDet(Z[w]))), w = dim-1 .. 1, -1); Trace(Z[1]) end proc
> 

LaPlace := proc (M::Matrix) local c; add((-1)^(c+1)*M[1, c]*Minor(M, 1, c), c = 1 .. ColumnDimension(M)) end proc
> 

dim := 7; A := Matrix(dim, dim, shape = symmetric, symbol = a)

7

 (1)
> 

start_time := time(); st := time[real](); Det1 := abs(A); CPUtime_used_Build_in_Determinant := time()-start_time; REALtime_used_Build_in_Determinant := time[real]()-st; start_time := time(); st := time[real](); Det2 := DetDef(A); CPUtime_used_Jeremy_Johnson_Determinant := time()-start_time; REALtime_used_Jeremy_Johnson_Determinant := time[real]()-st; start_time := time(); st := time[real](); Det3 := Dodgsonseq(A); CPUtime_usedDodgsonseq := time()-start_time; REALCPUtime_usedDodgsonseq := time[real]()-st; start_time := time(); st := time[real](); Det4 := Dodgson(A); CPUtime_usedDodgson := time()-start_time; REALtime_usedDodgson := time[real]()-st; start_time := time(); st := time[real](); Det5 := LaPlace(A); CPUtime_usedLaPlace := time()-start_time; REALtime_usedLaPlace := time[real]()-st; simplify(Det1-Det2); simplify(Det1-Det3); simplify(Det1-Det4); simplify(Det1-Det5)
``

0.32e-1

  

0.34e-1

  

0.93e-1

  

.108

  

47.094

  

41.295

  

40.766

  

38.158

  

0.31e-1

  

0.50e-1

  

0

  

0

  

0

  

0

 (2)

Download test_Determinants_symbolic.mw
Please Wait...