MathGroup Archive 2003

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: simple equation system -- crashing M5?

  • To: mathgroup at smc.vnet.net
  • Subject: [mg44270] Re: [mg44256] simple equation system -- crashing M5?
  • From: Daniel Lichtblau <danl at wolfram.com>
  • Date: Tue, 4 Nov 2003 03:23:39 -0500 (EST)
  • References: <200310310801.DAA09918@smc.vnet.net>
  • Sender: owner-wri-mathgroup at wolfram.com

Rene Brueck wrote:
> 
> Quite frankly, I'm stymied ... the equation system below manages to fry
> Mathematica 5 on my system.
> It starts of (more or less) fine, using about 2.2GB ram, before---rather
> suddenly--Mathematica vanishes from the screen ... no error message, no
> Kernel shutdown, no output, no save ... ziltsch
> 
> Has anyone had such an experience?? Any ideas??
> 
> Here's the equation system:
> 
> Solve[{M0 == (1 - f1 - f2 - f3 - f4 - f5 - f6 - f7 - f8 - f9 - f10 - f11 -
> f12 - f13 - f14 - f15 - f16)*m0,
> 
> M1 == f1*m0 + (1 - f1 - f2 - f3 - f4 - f5 - f6 - f7 - f8 - f9 - f10 - f11 -
> f12 - f13 - f14 - f15 - f16)*m1,
> 
> M2 == f1*m1 + f2*m0 + (1 - f1 - f2 - f3 - f4 - f5 - f6 - f7 - f8 - f9 -
> f10 - f11 - f12 - f13 - f14 - f15 - f16)*m2,
> 
> M4 == f1*m3 + f2*m2 + f3*m1 + f4*m0,
> 
> M5 == f2*m3 + f3*m2 + f4*m1 + f5*m0,
> 
> M6== f3*m3 + f4*m2 + f5*m1 + f6*m0,
> 
> M7== f4*m3 + f5*m2 + f6*m1+ f7*m0,
> 
> M8== f5*m3 + f6*m2 + f7*m1+ f8*m0,
> 
> M9== f6*m3 + f7*m2 + f8*m1+ f9*m0,
> 
> M10== f7*m3 + f8*m2 + f9*m1+ f10*m0,
> 
> M11 == f8*m3 + f9*m2 + f10*m1 + f11*m0,
> 
> M12 == f9*m3 + f10*m2 + f11*m1 + f12*m0,
> 
> M13== f10*m3 + f11*m2 + f12*m1 + f13*m0,
> 
> M14== f11*m3 + f12*m2 + f13*m1+ f14*m0,
> 
> M15== f12*m3 + f13*m2 + f14*m1+ f15*m0,
> 
> M16== f13*m3 + f14*m2 + f15*m1+ f16*m0},
> 
> {f1, f2, f3, f4, f5, f6, f7, f8, f9, f10, f11, f12, f13, f14, f15, f16}]

You are doing a fairly large symbolic row reduction. Internally, it is
the following matrix.

mat = {
 {-m0, -m0, -m0, -m0, -m0, -m0, -m0, -m0, -m0, -m0, -m0, -m0,
	-m0, -m0, -m0, -m0, m0 - M0},
 {-m1, -m1, -m1, m0 - m1, -m1, -m1, -m1, -m1, -m1, -m1, -m1, 
	-m1, -m1, -m1, -m1, -m1, m1 - M1},
 {-m2, -m2, -m2, m1 - m2, m0 - m2, -m2, -m2, -m2, -m2, -m2,
	-m2, -m2, -m2, -m2, -m2, -m2, m2 - M2}, 
 {0, 0, 0, m3, m2, m1, m0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -M4}, 
 {0, 0, 0, 0, m3, m2, m1, m0, 0, 0, 0, 0, 0, 0, 0, 0, -M5}, 
 {0, 0, 0, 0, 0, m3, m2, m1, m0, 0, 0, 0, 0, 0, 0, 0, -M6}, 
 {0, 0, 0, 0, 0, 0, m3, m2, m1, m0, 0, 0, 0, 0, 0, 0, -M7}, 
 {0, 0, 0, 0, 0, 0, 0, m3, m2, m1, m0, 0, 0, 0, 0, 0, -M8}, 
 {0, 0, 0, 0, 0, 0, 0, 0, m3, m2, m1, m0, 0, 0, 0, 0, -M9}, 
 {0, 0, 0, 0, 0, 0, 0, 0, 0, m3, m2, m1, m0, 0, 0, 0, -M10}, 
 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, m3, m2, m1, m0, 0, 0, -M11}, 
 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, m3, m2, m1, m0, 0, -M12}, 
 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, m3, m2, m1, m0, -M13}, 
 {0, 0, m0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, m3, m2, m1, -M14}, 
 {0, m0, m1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, m3, m2, -M15}, 
 {m0, m1, m2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, m3, -M16}};

The symbolic swell in the process of symbolic row reduction is immense.
When I do RowReduce on this it takes about 21 seconds on my machine and
gives a result of leaf count 421486988. The byte count very likely
exceeds 10 times that figure, or more than 4 GB.

You can reduce this, at slight loss of speed, via use of
Method->OneStepRowReduction in RowReduce. For this I get a leaf count of
95538570 and a byte count of 1625076320. To do similarly directly from
Solve, I did as below.

In[1]:= polys = {
	(1 - f1 - f2 - f3 - f4 - f5 - f6 - f7 - f8 - f9 - f10 - f11 -
	  f12 - f13 - f14 - f15 - f16)*m0 - M0,
	f1*m0 + (1 - f1 - f2 - f3 - f4 - f5 - f6 - f7 - f8 - f9 - f10 - f11 -
	  f12 - f13 - f14 - f15 - f16)*m1 - M1,
	f1*m1 + f2*m0 + (1 - f1 - f2 - f3 - f4 - f5 - f6 - f7 - f8 - f9 -
	  f10 - f11 - f12 - f13 - f14 - f15 - f16)*m2 - M2,
	f1*m3 + f2*m2 + f3*m1 + f4*m0 - M4,
	f2*m3 + f3*m2 + f4*m1 + f5*m0 - M5,
	f3*m3 + f4*m2 + f5*m1 + f6*m0 - M6,
	f4*m3 + f5*m2 + f6*m1+ f7*m0 - M7,
	f5*m3 + f6*m2 + f7*m1+ f8*m0 - M8,
	f6*m3 + f7*m2 + f8*m1+ f9*m0 - M9,
	f7*m3 + f8*m2 + f9*m1+ f10*m0 - M10,
	f8*m3 + f9*m2 + f10*m1 + f11*m0 - M11,
	f9*m3 + f10*m2 + f11*m1 + f12*m0 - M12,
	f10*m3 + f11*m2 + f12*m1 + f13*m0 - M13,
	f11*m3 + f12*m2 + f13*m1+ f14*m0 - M14,
	f12*m3 + f13*m2 + f14*m1+ f15*m0 - M15,
	f13*m3 + f14*m2 + f15*m1+ f16*m0 - M16};
                                                                                                                                                        
In[2]:= vars = {f1, f2, f3, f4, f5, f6, f7, f8, f9, f10, f11, f12, f13,
f14, f15, f16};

In[3]:= SetOptions[RowReduce, Method->OneStepRowReduction];

In[4]:= Timing[sol = Solve[polys==0, vars];]

While this may not quite choke the machine, it seems likely to be too
unwieldy to use in any significant way.

One of the projects I hope to tackle at some point is to figure out how
to cut down on the component of swell that arises, in effect, in the
"back substitution" phase of the Gaussian elimination. But offhand I do
not know whether that will have beneficial impact on this particular
example. It looks interesting so I'll keep it in my test suite.


Daniel Lichtblau
Wolfram Research


  • Prev by Date: Trying to use Mathematica as "word processor" for my math homework
  • Next by Date: Line and Polygon
  • Previous by thread: Re: simple equation system -- crashing M5?
  • Next by thread: Re: simple equation system -- crashing M5?