Re: [genius-list] Genius Future:

From: Squeak <squeak_at_xirr.com>
Date: Wed, 8 Sep 1999 03:42:54 -0400 (EDT)

On Wed, 8 Sep 1999 njh_at_cs.monash.edu.au wrote:

> On Wed, 8 Sep 1999, Squeak wrote:
>
> Excite found: www.mupad.de

Thanks

> > To demonstrate
> > need: "a@(10000,10000)=4" hangs genius, and "a=[0] ; a@(100,100)=4 ;
> > a@(10000,10000)=5" gets a fatal memory error.
>
> Yep, but what if you want to do something useful, like reduce to upper
> triangular form? You will need to store lots of intermediate values.
> There are nice algorithms for this and looking around wouldn't hurt.

Ok, so my numerical prelims are end of next year (spr'01) and I don't
know much about it, but: I was under the impression that for large n>10k
matricies that are sparse, one generally doesn't keep much of the matrix
anywhere (not even in swap or something) and one uses approx. methods
that don't need to do nearly so many intermediate calcs (such as a
whole matrix) and that the mem. space saved by using these methods is
astronomical (especially for n>1mil). Thus the fact that genius bombs
on a 2 non-zero element matrix is a sign that ti doesn't handle
sparse matricies in an efficient fashion.

I'll ask around (several of the guys who wrote LAPack teach here) and
see what comes up. I only suggest this because I am writing functions
as matricies, and for some things I use the coordinate as a hash into
a table fo pre-computed results (for recursive functions generally).

Thus starting a small trend into using hashes to lookup values seemed
like a good idea for someone to try. But I'll ask around in the numerics
dept. to see how the professionals do it.

> Except there is nothing that a partial order adds beyond a semigroup :-)
> Hence my working on semigroups...

Out of curiosity, given a partial order how (and if its not clear, why) do
i construct a semigroup. I can kinda see how to construct a partial order
from a semigroup, but the reverse seems harder to me.

(btw i said a tree for a partial order, because a partial order is (a set
of connected) tree (s) and doing the comparison would be fairly easy
in a tree (linear with depth) ... if this semi-group identification
thingy even allows you to compare elements then obviously that would be
better than a tree :)

> > ** Important question: is the source available? cvs or something?
For new genius stuff, specifically, but I'll check out yours too.

> > Polynomial rings,
> Is Eisenstein irreducibility computable? This would be useful.

Yeah it's a bunch of gcd's so it might be slow. (Compute gcd of all
non leading components, prime factorize gcd, throw out all primes with
powers greather than 1, check for non-divisiblity into leading
coefficient, naive impl. could be speeded up a little at least)

But eisenstein only tells if certain elem. are irreducible. It remains
silent on alot (most?) irreducible elements. I'd have to look up a
multi-variable version... it's late and the 2 variable problem looks
incomputable, but I might be dumb.

> > quotient spaces,
> What about them?

Just be able to quotient out any finitely generated sub space by
mod'ing out its generators. So the mod n is on the right track,
we could also have "5x^2+3x+1 mod x^2 + x +1 mod 2" as an element
in the field of 4 elements.

They should simply have +,- * and in some cases /. might be nice
to have is_prime, is_irreducible, gcd's , solving of crt's. But i'd be
happy if genius just supported the polynomials and modulo. We agree
that "mod n" should really do the inverse of a member (as per your reply
to the quirklist). No reason not to keep having modulo when it exists.

When I was working on some module research virtually every example we
needed could be done by some direct sum of z[x] mod something. Thus I'm a
fan of having them in there.

> > finite fields
> Fits under semigroups

Maybe... I don't want to make a cayley table for f_2^256 :) I don't know
how you are doing semi-groups tho. As long as I can specify an operator
overload type thing, I'd be happy i guess.

Also in general semi-groups have quotient structures (like several diff.
ones) If you aren't doing groups as a somewhat seperate entity (like a higher
order one) then we might want to look into some of those equivalence
relations (I think one might be: if M is a sub semi-group of G, then
m = n (mod M) if there exists g,h in M such that m+g = n+h).
I was very spoiled when I worked in this area tho, commutative monoids
were as bad as it got for me.

> > Interval arithmetic
> That would be very useful!

Yup yup. I plan on doing this more near the time I actually have to take
an error analysis class, but with your semi-group foundation work I
could probably add it easily? Operator overload and what not ..

> > Recursion
> ? You mean f(x) = x*f(x-1) - doesn't genius already do this
> > infinite (really infinite in the greek sense) sequences,
> Presumably defined as f(i)?

Presumably I'm just dumb, but genius crashes when I try that. Genius
always crashes when i do anything recursive.

Show me a working example, tho. I might just be being dumb.

> > basic algebraic stuff (variables are treated like unknown quantities
> > and kept throughout a calculation, first step imho).
>
> Done.

In genius or in your thingy?

In genius:
c=a+b; a=5; b=6; c
yields (a+b)

A bit tooo symbolic, I would like to see 11 :)

> > Functionals
> ? Aren't they just a special form of function(\omega->R ?)

I don't think so ( isn't L^\infty(R) uncountable ?) ....
At any rate, I just mean functions that take functions as arguments.
And also, it'd be nice to have functions that returned funcitons.
You can kinda do this with genius, but its not as easy as i'd like (or
maybe i'm just dumb and there is an easier way).

Ex. |f| = sup {f(x) : x in R } is a functional from the set of
bounded functions to R.

Ex. |f| =max { x : measure({ a: f(a) > x }) = 0 } is a functional
from L^\infty to R. I don't think \omega is big enough to to be
the domain of | * |.

> > curryable functions
> ? Aren't all functions curryable - once you have variable argument lists.

2 answers:

1. in genius i dont think ANY function is curryable directly.

2. I thought all functions were curryable, but if you let f(x,y) be
identical with f((x,y)) (in other words a function of 2 variables is a
function of one ordered pair) then I think you get into trouble with
functions of more than one matrix. I did at least, could be dumb tho.
Oh and I officially think it's dumb to distinguish between (x,(y,z))
and ((x,y),z) in practice (though in theory you would first prove that
the sets were iso in an obvious way :)

> > functions as transformation rules
> ? explain

Maybe pattern matching might have been a better name.

Basically a function has an argument and looks through its definitions
for a defitinition that will match the argument, and then applies that
definiton. This is merely an extension to my earlier ideas that
seems to me to be frought with problems. At any rate I haven't succeeded
in making it make sense.

An example might be piecewise functions "Let n in Z ;f(2*n) = n ;
f(2*n+1) = n" basically it checks to see if the argument fits the pattern
of the given argument, blah blah. Prolly a dumb idea, jsut use an if
statement inside the function, blah blah.

> > quarternions, matricies over skew fields
> c.v. fields :-)

Nod, I think this is where we are thinking alike ... :) Basically
I want your semi-groups to be primitives that can be used in
all the other structures we have ( vectors, matricies, modulo ,poly's).

> > And of course: a couple graphing type extensions that are total hack.
> Why would they need to be hacks? Could a graph be simply a
> function(called graph) which returns an image?

They are total hacks because I don't write gui stuff. I'd maybe make them
actually useful to someone besides me if I knew how genius and geo were
interacting.

> > As it is right now, I'm just slowly writing my own (GPL) sub-genius
> Ok, well tell me when you finish it, and we'll start on the genius
> sym-manip.

Very cool. Is the sym-manip dependent on the semigroup stuff or vice
versa? My sub-genius is a little weak on adding new "numbers" like
interval arith. or arbitrary semi-groups. If I had a stronger base to
work on, the compiler could be alot simpler. Right now type conversions
and other type issues are dominating my problems. If the semigroup stuff
could alleve that, I'd be very happy to work with it.
Received on Wed Sep 08 1999 - 00:19:08 CDT

This archive was generated by hypermail 2.2.0 : Sun Apr 17 2011 - 21:00:02 CDT