how to solve a symbolic matrix 11x11? memory allocation problems

User login

Collaborative Books

Syndicate

how to solve a symbolic matrix 11x11? memory allocation problems

Posted on 2008-07-31 05:41 By saberworks (6)

Categories:

How do I ...? with Maple

I have a symbolic matrix (11x11) it is sparsely populated with components on the diagonal and 2 places either side. When I have tried to calculate the [standar operations > nverse] (on a PC with Raid 0 and 4 Gb) Maple 12 stops running at 1883 Mb and complains about 'memory allocation?

Q1: how do I (inexperienced maple user) increase memory allocation?

Q2: when I tried to run a 5x5 matrix as a test a matrix wasn't returned, only a list of letters?

What is your exact configuration?

Comment on 2008-07-31 10:27 from gulliet (

99)

Could you be more specific about your configuration? You seem to imply that you are working on a 64-bit platform (assuming you are talking about 4 GB of physical RAM and not of virtual memory), while the error reported suggest that you are using a 32-bit version of Maple xx.x (not being able to go beyond 2 GB of memory).

Details such as operating system, Maple version, 32- or 64- bit hardware, etc., might be crucial to answer your question.

Regards,
-- Jean-Marc

spec

Comment on 2008-07-31 11:18 from saberworks (6)

Its running 32 bit maple on a 64 bit system. When I tried running 32 bit maple on a 32 bit machine maple fails at around 909Mb (1GB of ram). How do I reallocate the memory avavaible. As there are many 32bit machines with large amounts of ram (performance based workstations) or is maple held back by it's kernel design?

saberworks

Memory fragmentation, perhaps?

Comment on 2008-07-31 12:23 from gulliet (

99)

I am not familiar with Maple's kernel design, but I believe that Maple (similar to this respect to many other CAS) uses contiguous array of memory location to store object such as matrices. Say Maple needs 400 MB to store an intermediate result during a computation. Maple will request to the operating system a 400 MB contiguous chunk of memory. If the operating system cannot find any available contiguous peace of memory of at least this size, the allocation will failed, and Maple will report "not enough memory" (being understood "not enough contiguous memory" in this case).

Depending on the operating system you are using, you may find a variety of software that optimize or defragment memory.

Regards,
-- Jean-Marc

not really

Comment on 2008-07-31 12:33 from acer ( Maple Rating 4

1357)

Maple stores a Matrix entirely in (only some) contiguous memory block only in the cases of hardware datatypes (float[8], complex[8], integer[4], etc) and perhaps immediate integers. For Matrices with symbolic expressions as the entries, the stored entries will point to locations for those objects. Those individual symbolic expressions represented in the Matrix entries may well be scattered throughout Maple's allocated memory.

acer

Example of a 5x5 matrix

Comment on 2008-07-31 12:10 from gulliet (

99)

Could you post an example of what you did (actual commands you used). For instance, for Q2, a 5x5 matrix with the Maple commands and the output. It would be easier to check what's went wrong (Q2 suggests you made a mistake either in the matrix itself or in the command to manipulate it).

    |\^/|     Maple 12 (IBM INTEL NT)
._|\|   |/|_. Copyright (c) Maplesoft, a division of Waterloo Maple Inc. 2008
 \  MAPLE  /  All rights reserved. Maple is a trademark of
 <____ ____>  Waterloo Maple Inc.
      |       Type ? for help.
> with(LinearAlgebra):
> M := Matrix([[a, 0, f, 0, 0], [0, b, 0\
> , 0, 0], [0, 0, c, 0, 0], [0, 0, 0, d, 0], [0, 0, 0, g, e]]);
                              [a    0    f    0    0]
                              [                     ]
                              [0    b    0    0    0]
                              [                     ]
                         M := [0    0    c    0    0]
                              [                     ]
                              [0    0    0    d    0]
                              [                     ]
                              [0    0    0    g    e]

> MatrixInverse(M);
                     [                 f                 ]
                     [1/a     0     - ---      0       0 ]
                     [                c a                ]
                     [                                   ]
                     [ 0     1/b      0        0       0 ]
                     [                                   ]
                     [ 0      0      1/c       0       0 ]
                     [                                   ]
                     [ 0      0       0       1/d      0 ]
                     [                                   ]
                     [                          g        ]
                     [ 0      0       0      - ---    1/e]
                     [                         d e       ]

Regards,
-- Jean-Marc

purpose

Comment on 2008-07-31 12:38 from acer ( Maple Rating 4

1357)

Do you mean that you have a tridiagonal 11x11 Matrix where each and every entry (in the main, first sub-, and first super-diagonal) are nonzero and consist of distinct variable names?

I could envision that the general inverse of such a Matrix would contain entries with very large symbolic expressions in them. At each pivoting step of LU or Gaussian elimination, say, a division involving the previous row's large symbolic expression will result in the current row having even more complicated long expressions. I don't see that tridiagonality in itself would prevent that. Do the entries involve just a few names, or are you really trying to do it for the general form, with a distinct name for each nonzero entry? This could well be the sort of problem where the size of expressions in such a general result increase in length quickly, as the size of the Matrix rises. And It might take many pages just to print it.

So I would ask, what do you plan on doing with the solution? If you plan on substituting values into the solution then you might be better off switching that order of tasks: first instantiate, then solve.

acer

oh

Comment on 2008-07-31 13:35 from acer ( Maple Rating 4

1357)

Oh, maybe the length is not so bad after all, on account of the structure.

> p := proc(n, x)
> local res, i;
>   res := Matrix(n, n);
>   for i to n do res[i, i] := x[i, i] end do;
>   for i to n - 1 do
>     res[i + 1, i], res[i, i + 1] := x[i + 1, i], x[i, i + 1]
>   end do;
>   res
> end proc:

> p(3,t);
                        [t[1, 1]    t[1, 2]       0   ]
                        [                             ]
                        [t[2, 1]    t[2, 2]    t[2, 3]]
                        [                             ]
                        [   0       t[3, 2]    t[3, 3]]
 
> length(LinearAlgebra:-MatrixInverse(p(3,t)));
                                     1464
 
> length(LinearAlgebra:-MatrixInverse(p(11,t)));
memory used=122.4MB, alloc=9.2MB, time=4.37
                                    2610924

So now I'd ask, what commands were tried, that led to the huge memory use? Could the code be posted?

acer

foiled again

Comment on 2008-07-31 14:23 from acer ( Maple Rating 4

1357)

I did the above in the commandline (TTY) interface. Besides not having to do 2D Math typesetting of the results, that interface also has default support for common subexpression representation in the output.

Then I tried LinearAlgebra:-MatrixInverse(p(10,t)) in the Maple 12 Standard Java GUI. Maple can compute that result in a few seconds. But the Standard GUI is still chugging away on it after even a few minutes. And the GUI itself is using a lot of memory (500MB at this point).

Now, I don't know whether the huge amount of time and memory that the Standard GUI is using to display the result for size n=10 is due to lack of common subexpression labelling or to 2D Math output typesetting. But the TTY interface takes just a few pages to display it, with common subexpression labelling.

The Standard GUI also issued a slew of Java error messages to my console, starting with, `Exception in thread "Timer-1" java.lang.OutOfMemoryError: Java heap space'. As I type this, that example is still stalled on printing, and the Standard GUI is white (blank) and hence unresponsive. I shall have to kill the session (without being able to save the worksheet).

I tried it in Maple's Classic graphical interface. It worked beautifully.

acer

DAGs

Comment on 2008-08-01 13:24 from JacquesC ( Maple Rating 4

1697)

There were excellent reasons for the original Maple designers to use DAGs in the kernel, and for the original writers of the pretty-printer to follow suit. It was presumptuous of the writers of the new pretty-printer to think that they knew better and could turn off this feature without paying the cost. This example is a perfect example of this.

Problem Details

Comment on 2008-07-31 15:18 from saberworks (6)

I'm new to maple - so I will attempt to explain as much as i can what i've done.

When I open maple I get a worksheet area on the right. I started a symbolic matrix 11x11 and filled it in. I then right clicked on the matrix click standard operations and then clicked on inverse. (where maple quickly grinds to a halt at 1883 Mb). I don't know where i can drive maple similare to matlab.

My matrix structure looks like this (where the diag (Z) are 4 symbols deep)

Z, X, X, 0, 0, 0, 0, 0, 0, 0, 0
X, Z, X, X, 0, 0, 0, 0, 0, 0, 0
X, X, Z, X, X, 0, 0, 0, 0, 0, 0
0, X, X, Z, X, X, 0, 0, 0, 0, 0
0, 0, X, X, Z, X, X, 0, 0, 0, 0
0, 0, 0, X, X, Z, X, X, 0, 0, 0
0, 0, 0, 0, X, X, Z, X, X, 0, 0
0, 0, 0, 0, 0, X, X, Z, X, X, 0
0, 0, 0, 0, 0, 0, X, X, Z, X, X
0, 0, 0, 0, 0, 0, 0, X, X, Z, X
0, 0, 0, 0, 0, 0, 0, 0, X, X, Z

I will try to post the real matrix data soon.

Thanks for everyone's efforts.

saberworks

How can i run my problem as

Comment on 2008-07-31 15:20 from saberworks (6)

How can i run my problem as a script and post my commandline expressions. Can I then run the script without opening the GUI and run faster?

Command line

Comment on 2008-07-31 15:50 from alec ( Maple Rating 4

1476)

You don't need a script - just do it in a command line maple as acer suggested. Also, put a : at the end instead of the ; to avoid printing the result.

Alec

Use dummy symbols first

Comment on 2008-07-31 16:12 from gulliet (

99)

I would suggest to do the inversion with dummy symbols and then to replace these symbols by their actual symbolic expressions.

> with(LinearAlgebra):
> M := Matrix([[Z, X, X, 0, 0, 0, 0, 0, 0, 0, 0], [X, Z, X, X, 0, 0, 0, 0, 0, \
> 0, 0], [X, X, Z, X, X, 0, 0, 0, 0, 0, 0], [0, X, X, Z, X, X, 0, 0, 0, 0, 0],\
>  [0, 0, X, X, Z, X, X, 0, 0, 0, 0], [0, 0, 0, X, X, Z, X, X, 0, 0, 0], [0, 0\
> , 0, 0, X, X, Z, X, X, 0, 0], [0, 0, 0, 0, 0, X, X, Z, X, X, 0], [0, 0, 0, 0\
> , 0, 0, X, X, Z, X, X], [0, 0, 0, 0, 0\
> , 0, 0, X, X, Z, X], [0, 0, 0, 0, 0, 0, 0, 0, X, X, Z]]);
               [Z    X    X    0    0    0    0    0    0    0    0]
               [                                                   ]
               [X    Z    X    X    0    0    0    0    0    0    0]
               [                                                   ]
               [X    X    Z    X    X    0    0    0    0    0    0]
               [                                                   ]
               [0    X    X    Z    X    X    0    0    0    0    0]
               [                                                   ]
               [0    0    X    X    Z    X    X    0    0    0    0]
               [                                                   ]
          M := [0    0    0    X    X    Z    X    X    0    0    0]
               [                                                   ]
               [0    0    0    0    X    X    Z    X    X    0    0]
               [                                                   ]
               [0    0    0    0    0    X    X    Z    X    X    0]
               [                                                   ]
               [0    0    0    0    0    0    X    X    Z    X    X]
               [                                                   ]
               [0    0    0    0    0    0    0    X    X    Z    X]
               [                                                   ]
               [0    0    0    0    0    0    0    0    X    X    Z]

> MatrixInverse(M);
memory used=15.2MB, alloc=4.5MB, time=0.67
memory used=19.0MB, alloc=4.6MB, time=0.87
memory used=22.9MB, alloc=4.6MB, time=1.13
memory used=26.7MB, alloc=4.6MB, time=1.30

[... actual output of the matrix discarded ...]

-- Jean-Marc

not best

Comment on 2008-07-31 17:03 from acer ( Maple Rating 4

1357)

I would suggest not doing that, if avoidable. The masking of the actual entries by dummy names may lead to use of a "hidden zero" as a pivot during computation of the inverse. If that happened (though perhaps quite unlikely) then the result would be incorrect. Zeros could appear in denominators upon resubstitution and unmasking of the actual entries, with numeric exception error ensuing.

But now we know that the actual entries are not just simple names, even if they recur with a given structure. So is the huge memory use due to printing of results, or perhaps also due to computational grind during the inversion? Instead of doing the inversion using a context-menu, as was described, do it by issuing the relevant command. And suppress printing of the output, terminating that command with a colon instead of a semicolon (as alec suggested).

The code in question could also be uploaded to this site, using its File Manager.

acer

Assuming you run Windows

Comment on 2008-07-31 15:48 from gulliet (

99)

Assuming you run Windows: "Start" -> "All Programs" -> "Maple 12" -> "Command-line Maple 12"

Regards,
-- Jean-Marc

Here is my

Comment on 2008-08-01 06:01 from saberworks (6)

Here is my problem

********************

with(LinearAlgebra);

M := Matrix([[R1+R2+R3+RL2, R3, -R2, 0, 0, 0, 0, 0, 0, 0, 0], [R3, R3+R4+R5+RL2, 0, -R4, 0, 0, 0, 0, 0, 0, 0], [-R2, 0, R2+R6+R7+R8, R8, -R7, 0, 0, 0, 0, 0, 0], [0, -R4, R8, R4+R8+R9+R10, 0, -R9, 0, 0, 0, 0, 0], [0, 0, -R7, 0, R7+R11+R12+R13, R13, -R12, 0, 0, 0, 0], [0, 0, 0, -R9, R13, R9+R13+R14+R15, 0, -R14, 0, 0, 0], [0, 0, 0, 0, -R12, 0, R12+R16+R17+R18, R18, -R17, 0, 0], [0, 0, 0, 0, 0, -R14, R18, R14+R18+R19+R20, 0, -R19, 0], [0, 0, 0, 0, 0, 0, -R17, 0, R17+R21+R22+R23, R23, -R22], [0, 0, 0, 0, 0, 0, 0, -R19, R23, R19+R23+R24+R25, -R24], [0, 0, 0, 0, 0, 0, 0, 0, -R22, -R24, R22+R24+R26]]);

MatrixInverse(M);

********************

Matrix inverse throws memory allocation warning and stops running. I know it will be big, but expect it to at least use all avavilable memory first. Is there a memory allocation switch/config to override or instruct maple to use XXGb memory?

saberworks

Failed on a 64-bit system

Comment on 2008-08-01 08:32 from gulliet (

99)

FWIW,

    |\^/|     Maple 11 (APPLE UNIVERSAL OSX)
._|\|   |/|_. Copyright (c) Maplesoft, a division of Waterloo Maple Inc. 2007
 \  MAPLE  /  All rights reserved. Maple is a trademark of
 <____ ____>  Waterloo Maple Inc.
      |       Type ? for help.
> with(LinearAlgebra): 
> M := Matrix([[R1+R2+R3+RL2, R3, -R2, 0\                                      
> , 0, 0, 0, 0, 0, 0, 0], [R3, R3+R4+R5+\                                      
> RL2, 0, -R4, 0, 0, 0, 0, 0, 0, 0], [-R\                                      
> 2, 0, R2+R6+R7+R8, R8, -R7, 0, 0, 0, 0\                                      
> , 0, 0], [0, -R4, R8, R4+R8+R9+R10, 0,\                                      
>  -R9, 0, 0, 0, 0, 0], [0, 0, -R7, 0, R\                                      
> 7+R11+R12+R13, R13, -R12, 0, 0, 0, 0],\                                      
>  [0, 0, 0, -R9, R13, R9+R13+R14+R15, 0\                                      
> , -R14, 0, 0, 0], [0, 0, 0, 0, -R12, 0\                                      
> , R12+R16+R17+R18, R18, -R17, 0, 0], [\                                      
> 0, 0, 0, 0, 0, -R14, R18, R14+R18+R19+\                                      
> R20, 0, -R19, 0], [0, 0, 0, 0, 0, 0, -\                                      
> R17, 0, R17+R21+R22+R23, R23, -R22], [\                                      
> 0, 0, 0, 0, 0, 0, 0, -R19, R23, R19+R2\                                      
> 3+R24+R25, -R24], [0, 0, 0, 0, 0, 0, 0, 0, -R22, -R24, R22+R24+R26]]):
> MatrixInverse(M):
bytes used=4009260, alloc=2948580, time=0.12
bytes used=8344364, alloc=5438492, time=0.23
bytes used=12654928, alloc=6224780, time=0.49
bytes used=16669052, alloc=7731832, time=0.70

[snip]

bytes used=1320241168, alloc=407493756, time=362.80
bytes used=1363205652, alloc=439666040, time=369.52
bytes used=1409908468, alloc=484418932, time=373.20
Execution stopped: Memory allocation failed.
Please see ?alloc for more detail.

Regards,
-- Jean-Marc

Memory Allocation Errors (Online Documentation)

Comment on 2008-08-01 08:39 from gulliet (

99)

might contains some useful information on memory management.
Evaluate ?alloc or search for alloc.

Here is a sample:

Memory Limits
Maple has two types of memory limits: software limits and hardware limits.
Software limits are imposed by the -T command-line argument, the datalimit argument to kernelopts and system imposed user limits (for example shell limits).
The hardware limit is the amount of physical memory available on the system.

-- Jean-Marc

symbolic linear algebra

Comment on 2008-08-15 12:11 from roman_pearce ( Maple Rating 4

505)

You can disable a lot of the arithmetic and normalization and use a heuristic test for zero to speed things up:

Normalizer := proc(a) a end proc:
TestZero := testeq:
A := LinearAlgebra:-MatrixInverse(M):

Granted, the result is probably now 10 times more useless.

i cannot find any examples

Comment on 2008-08-01 08:47 from saberworks (6)

i cannot find any examples of defining memory limits (for the software)

maple.exe -T datalimit 4000000 ??

this is why i posted. Glad that you now have the same result. Hopefully someone will no the switch/flag command to force maple to use a XXXX Mb memory limit.

saberworks

the inverse is dense

Comment on 2008-08-01 13:12 from Axel Vogt ( Maple Rating 4

948)

Not that I am going to prove it, but if the inverse is dense,
then I would guess it may be a quite complicated expression.

Here is a way to check it on test values:

  restart; 
  interface(rtablesize=14); with(LinearAlgebra); Digits:=14;

  m:=RowDimension(M);
  indets(M): L:=convert(%,list); k:=nops(%);

  # the Matrix is of dim=14, you have 27 variables
  # set them to some values

  R:=RandomTools[Generate](list( integer(range=-20..20), k));
  data:=[seq( L[i]=R[i], i=1..k)];

  N:=eval(M,data); 
  Q:=MatrixInverse(N);

Then Q is returned almost immediately - and it is dense.

Indeed, I checked it with another CAS

Comment on 2008-08-01 14:28 from gulliet (

99)

I tried to compute the inverse matrix with another CAS and it took about 40 seconds to get the answer (the overall memory consumption was rather small). As Axel conjectured, the inverse matrix is, indeed, dense and each matrix entry is made of about 15,000 symbols.

To check that the returned matrix was correct, I computed the individual dot product line by column (i.e. M.M^(-1) split in 121 individual dot products so I could timed and checked them individually). It took between one and two minutes to compute and simplify to zero or one each dot product.

In[3]:= Timing[inv = Inverse[m];]

Out[3]= {37.2488, Null}

In[4]:= ByteCount[inv]

Out[4]= 34654736

In[5]:= LeafCount[inv]

Out[5]= 1852920

In[7]:= Map[LeafCount, inv, {2}]

Out[7]= {{17896, 17875, 16585, 15651, 15022, 15019, 14404, 14314, 
  13859, 13859, 13927}, {17878, 17896, 15654, 16583, 15049, 15034, 
  14385, 14432, 13904, 13917, 13984}, {16582, 15651, 16606, 16570, 
  15615, 15134, 14587, 14610, 14076, 14056, 14153}, {15654, 16586, 
  16576, 16606, 15138, 15606, 14638, 14597, 14059, 14082, 
  14158}, {15011, 15046, 15606, 15130, 17126, 16777, 15996, 15391, 
  14601, 14588, 14734}, {15028, 15040, 15133, 15615, 16777, 17126, 
  15391, 16002, 14589, 14604, 14736}, {14386, 14376, 14593, 14623, 
  15996, 15391, 17075, 16941, 15577, 15201, 15577}, {14326, 14444, 
  14633, 14603, 15391, 16002, 16941, 17075, 15201, 15578, 
  15578}, {13859, 13868, 14076, 14059, 14601, 14589, 15577, 15201, 
  16503, 16474, 17007}, {13859, 13872, 14056, 14082, 14588, 14604, 
  15201, 15578, 16474, 16503, 17007}, {13927, 13939, 14153, 14158, 
  14734, 14736, 15577, 15578, 17007, 17007, 18432}}

In[8]:= Mean[Flatten[%]]

Out[8]= 1852908/121

In[9]:= % // Round

Out[9]= 15313

In[10]:= Do[Print[p, " ", q, " ", 
  m[[p, All]].inv[[All, q]] // Simplify // Timing], {p, 11}, {q, 11}]

1 1 {116.241,1}

1 2 {72.5946,0}

1 3 {73.9493,0}

1 4 {65.2858,0}

1 5 {67.987,0}

1 6 {64.7355,0}

[snip]

-- Jean-Marc

Inverse matrix uploaded on MaplePrimes (mat.csv.gz)

Comment on 2008-08-01 18:32 from gulliet (

99)

I have uploaded the inverse matrix obtained with Mathematica as a CSV file compressed with GZIP on MaplePrimes, so you can import the matrix back into Maple.

Download 97_mat.csv.gz
View file details

HTH,
-- Jean-Marc

dim=6 already gives problems using Maple

Comment on 2008-08-02 15:35 from Axel Vogt ( Maple Rating 4

948)

  f:= (i,j) -> M[i,j]:
  smallM:=Matrix(5,f);

  MatrixInverse(smallM): #MatrixInverse(smallM, method='pseudo'); do not use pseudo!
  `length of entries`=map(length,%);
  #`example using data`=eval(%%,data);

For dim=5 the average entry has length ~ 20.000 characters, for dim=6 I aborted

Trying a Pari interface I gave up as well (due to time, memory, patients and skill).

Maple losing its speed edge?

Comment on 2008-08-03 07:10 from JacquesC ( Maple Rating 4

1697)

On problems like this, which are essentially just manipulation of lots of terms with nice normalization properties, Maple used to really shine. It was much faster than Mathematica, which translated to a lot of other parts of Maple that are manipulation-heavy also being faster.

Now, it could be that this one algorithm is badly written, so suffers from massive overhead. Or it could be that the state-of-the-practice has moved, and Maple has not. What about other systems?

Mathematica's and SAGE's speed

Comment on 2008-08-03 14:28 from alec ( Maple Rating 4

1476)

Mathematica puts everything that they can in the kernel. Every new release more and more of their code is transferred from Mathematica code to code in C.

SAGE does a similar thing. They are trying to rewrite Python code in Cython, which translates it to C (giving about 30 - 100 times increase in speed usually.)

Alec

Pari's speed

Comment on 2008-08-03 15:17 from Axel Vogt ( Maple Rating 4

948)

Well, I do not use it often in then I call it from Maple and aborted (after a longer time for dim=5).

Pari is written in C, so I guess that the algorithm counts (however have not tried to look for it).

}

how to solve a symbolic matrix 11x11? memory allocation problems

Comment viewing options