RE: Strategy for overly long computations?
- To: mathgroup at smc.vnet.net
- Subject: [mg35354] RE: Strategy for overly long computations?
- From: "DrBob" <majort at cox-internet.com>
- Date: Tue, 9 Jul 2002 06:49:22 -0400 (EDT)
- Reply-to: <drbob at bigfoot.com>
- Sender: owner-wri-mathgroup at wolfram.com
Well, you either know the values of those symbols, or you don't. If you
don't, they're unknown. Which ones you solve for in terms of others is
a separate issue. It's easier to solve for some than others, and easier
to eliminate some than others, but you still have 16 unknowns.
Anyway, the code I suggested gives a solution in 1 second on my machine:
eqns = {cn1, cn2, elim} // Simplify
eqns2 = eqns /. {x -> x + x1, y -> y + y1, z -> z +
z1} /. {x1 -> 0, y1 -> 0, z1 -> 0} // Simplify
Timing[s = Solve[eqns2, {x, y, z}];]
{1.062 Second, Null}
There are two solutions but I'll look at just one, and only the
expression for x. Check out the LeafCount, ByteCount, and Depth. I
also counted 5 square roots and 7 divisions, plus a lot of other powers:
t = s[[1, 1, 2]] // FullForm;
LeafCount[t]
ByteCount[t]
Depth[t]
Length@Position[t, Power[a_, #], Infinity] & /@ {1/2}~Join~Range[-1, 8]
11371
166016
16
{5, 7, 0, 15120, 2037, 202, 300, 20, 20, 0, 0}
In each case the denominator cannot be zero and the root needs a
positive argument (if you want real solutions). Roots of zero also give
separate cases. The denominators and root arguments are VERY
complicated, even in my simplified form of the problem.
Here's a count of additions, subtractions, and multiplications:
Length@Position[t, #[_,b_], Infinity] & /@ {Plus, Subtract, Times,
Rational}
{38, 7, 1132, 6}
But wait, that's only additions and multiplications of TWO terms only.
Here's a more complete count
ClearAll[count]
count[m_Integer] := Length@Position[t, #, {m}] &
Table[count[m] /@ {Plus, Times}, {m, 1, 16}]
Plus @@ %
{{0, 0}, {0, 1}, {1, 0}, {0, 3}, {2, 0}, {2, 16}, {5, 28}, {5, 50}, {4,
98}, {6, 168}, {1, 118}, {8, 42}, {4, 440}, {0, 168}, {0, 0}, {0, 0}}
{38, 1132}
So, in summary, that's a useless solution even if it's correct, and you
can't even be certain of that.
Simplify the problem!
Bobby
-----Original Message-----
From: Peter S. Shenkin [mailto:shenkin at mindspring.com]
To: mathgroup at smc.vnet.net
Subject: [mg35354] Re: Strategy for overly long computations?
Hi,
First, I tried again with Solve, rather than Reduce; after thinking
about
it, I decided that Solve should run faster, and it did -- taking 1.25
hours to run.
Second, I disagree with your concept that there are 16 unknowns, or 14
after elimination of the lm's. Seems to me that when you specify
{x,y,z}
as the 2nd arg to Solve, you're telling it that anything else is a
parameter
or symbol. Reduce has to take the domain effects of these parameters
into
account, but Solve doesn't -- which is why it's faster. But maybe
this is
what you were really saying. (?)
Also, the result of Eliminate is linear in x, y and z, I believe (the
symbols being solved for -- which I believe is the standard definition
of what we mean when we use the term "unknown" in discussing a system
of equations).
Anyway, the solution returned by Solve gives two {x,y,z} solutions,
each
taking over 100,000 lines to express, or >30K lines per variable (x, y
or
z).
Thanks for your help -- I will play with your suggestions in any case.
In
fact, I applied your change of variables in my efforts to solve the
thing by
hand, but I didn't have any reason to believe this would help
Mathematica.
--
work: shenkin at schrodinger.com = 100%
play: shenkin at mindspring.com = 0%
Peter S. Shenkin = Dull boy
--
----- Original Message -----
From: "DrBob" <majort at cox-internet.com>
To: mathgroup at smc.vnet.net
Subject: [mg35354] RE: Strategy for overly long computations?
> First of all, you have 16 unknowns, not 5 --- x, y, z, x1, x2, y1,
y2,
> z1, z2, r1, r2, xv, yv, zv, lm1, and lm2.
>
> Eliminating lm1 and lm2 brings it down to 14 variables, with 3
equations
> --- two quadratic and one of THIRD degree.
>
> I realize there's language in Help for Reduce and Solve about
variables
> and parameters, but there's no practical difference. Mathematica
still
> has to deal with all that dimensionality, with too few equations to
> reduce it. There are many, many, many special cases, with that many
> parameters.
>
> You can do a change of variables to make x1==x2==x3==0 in the new
> coordinate system:
>
> eqns /. {x -> x + x1, y -> y + y1, z -> z + z1} /. {x1 -> 0, y1 ->
0,
> z1 -> 0} // Simplify
> Solve[eqns2, {x, y, z}]
>
> (Solve worked quickly this time, but it's a very complicated
solution!)
>
> You might further reduce the problem by looking for symmetries. For
> instance, permutations of the three coordinates, accompanied by
> permutations of the associated parameters, don't matter, so you
could
> assume x2>y2>z2 or something like that. Reduce and Solve can't use
> assumptions, so that may not help. But keep looking for
> simplifications. Try this, for instance:
>
> I never let a calculation run more than two minutes if I don't have
good
> reason to think it will succeed. Try a smaller problem by falling
back
> to two dimensions, and see what happens.
>
> Bobby
>
> -----Original Message-----
> From: Peter S. Shenkin [mailto:shenkin at mindspring.com]
To: mathgroup at smc.vnet.net
> Sent: Monday, July 08, 2002 2:19 AM
> Subject: [mg35354] Strategy for overly long computations?
>
> Hi,
>
> I'm trying to solve a set of 5 eqns in 5 unknowns, three of which
> are quadratic and two of which are linear. I'm only interested
> in three of the unknowns, so first I eliminate the other two.
>
> So far, Mathematica 4.0 on an UltraSPARC has been grinding away for
> over 24 hours on this system at 96% of the CPU. There are no
> errmsgs.
>
> Does anyone out there have any insight into any of:
>
> 1. Whether this system is so tough it'll take "forever" to get
> through all the possibilities;
>
> 2. Whether there's some way of reorganizing the calculation so
> that Mathematica can work faster;
>
> 3. Whether I'm encountering some sort of bug or malfunction;
>
> 4. Whether I'm doing something really stupid.
>
> Thanks. The system is shown here; I'm running in background,
> redirecting stdin from a file with contents shown here. The
> calculation through the first Save is nearly immediate; almost
> all the time so far is taken up in the Reduce step.
>
> For clarity, let me say that I'm running the job as:
>
> math < intersect >& intersect.log &
>
> -------------------
> cn1 = ( x - x1 )^2 + ( y - y1 )^2 + ( z - z1 )^2 == r1^2
> cn2 = ( x - x2 )^2 + ( y - y2 )^2 + ( z - z2 )^2 == r2^2
> lgrx = ( x - xv ) + lm1 * ( x - x1 ) + lm2 * ( x - x2 ) == 0
> lgry = ( y - yv ) + lm1 * ( y - y1 ) + lm2 * ( y - y2 ) == 0
> lgrz = ( z - zv ) + lm1 * ( z - z1 ) + lm2 * ( z - z2 ) == 0
>
> lgrxyz = { lgrx, lgry, lgrz }
> elim = Eliminate[ lgrxyz, {lm1,lm2} ]
> eqns = { cn1, cn2, elim }
>
> Save[ "intersect.out", cn1, cn2, lgrx, lgry, lgrz, lgrzyx, elim,
eqns ]
>
> redn = Reduce[ eqns, {x,y,z} ]
> Save[ "intersect.out", redn ]
> soln = Solve[ eqns, {x,y,z} ]
> Save[ "intersect.out", soln ]
> -------------------
>
> -P.
>
> --
>
> work: shenkin at schrodinger.com = 100%
> play: shenkin at mindspring.com = 0%
> Peter S. Shenkin = Dull boy
>
> --
>
>
>
>
>