# [Maxima] simplifying sums of numbers

sen1 at math.msu.edu sen1 at math.msu.edu
Sat Dec 30 14:55:01 CST 2006

```OK,
Here is the real mathematical problem.

I have two polynomial maps \$F_1(x,y), F_2(x,y)\$ from the plane to the
plane. They have low degree, say 2 for now.

Given numbers \$a > 1, b > 1\$, I compute parametrized curves
\$C_1(t,n), C_2(t,n)\$  which have the form

\$\$ C_i(t,n) = (F_i)^n (a^(-n)*x, b^(-n)*y),  \ i = 1,2 \$\$

Here \$F_i^n\$ is the \$nth\$ iterate of \$F_i\$, so it has degree \$2^n\$.

In the actual mathematical problem at hand, it seems that most of the
coefficients of the polynomial iterates \$F_i^n\$ are small.  From
numerical calculations, it seems that Only about 10 or
12 are significant.

I am interested in computing the intersections of the curves

\$C_1(t,n), C_2(t,n)\$ in the unit square for \$n=12\$.

Bezout's estimate gives a (very crude) upper bound for the number of
intersections of \$2^{24}\$.   In my case, for other reasons, the actual
number intersections is likely to be around 500.  I want to find all
(or most ) of these intersections.

So, what is the best tool?

I found a package on CGAL which is called (something like "2d
Arrangements") which is written in C++.  This uses some sort of
"sweepout algorithms" to find the intersections of curves.  I haven't
yet implemented it.

Given this kind of problem, is it a waste of time to try to use
maxima?

Thanks for any suggestions.

-sen

On Sat, 30 Dec 2006, Richard Fateman wrote:

>
>
>> -----Original Message-----
>> From: maxima-bounces at math.utexas.edu
>> [mailto:maxima-bounces at math.utexas.edu] On Behalf Of sen1 at math.msu.edu
>> Sent: Saturday, December 30, 2006 8:11 AM
>
> ...
>
>
>>>
>>> For searching, a bipartition method could be fast enough:
>> first compare
>>> x with element in position length(z)/2, and take the inferior or
>>> superior half of pairs, and repeat this process until you find the
>>> interval.
>>>
>>> Does this help?
>>
>
> A suggestion, if this is to be fast, storing the elements in a LIST is a bad
> idea, because to get the element in position L takes L steps.  This converts
> a fast method (binary search which takes logarithmic time) into linear time.
> If you want to do linear time, just iterate down the list searching for the
> right interval in order.
>
> Allocating a proper array and sorting it is very easy in lisp; it can't be
> too hard in maxima.
> On the other hand, the linear time search might be so fast that you don't
> really need to do binary search at all.
>
> I don't know what the objective really is here, but there are lots of
> geometric computation packages, and I have recently looked at a
> computational vision package (associated with another version of lisp, LUSH)
> with lots of tools that probably include more general stuff than this, at
> least for numerical inputs.
>
>
>
>
> _______________________________________________
> Maxima mailing list
> Maxima at math.utexas.edu
> http://www.math.utexas.edu/mailman/listinfo/maxima
>

--
---------------------------------------------------------------------------
| Sheldon E. Newhouse            |    e-mail: sen1 at math.msu.edu           |
| Mathematics Department         |       				   |
| Michigan State University      | telephone: 517-355-9684                |
| E. Lansing, MI 48824-1027 USA  |       FAX: 517-432-1562                |
---------------------------------------------------------------------------
```