Re: [genius-list] Genius Future:

On Wed, 8 Sep 1999, Squeak wrote:

> 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.

Yup, this is essentially correct - generally sparse matrices are of a
special form(for numerical stuff anyway) which can be more effciently
handled.

> 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.

Yep, this would be very good!

> > 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.

define ab = a iffi a <= b

Not all semigroups form partial orders.

> (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 :)

No it will be somewhat slower, but semigroups include equivalences,
groups, partial orders, rings, fields, (semi-)lattices and basically
anything else with a binary op(not surprising when a semi-group only has 1
requirement - namely associativity)

> > > 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.

It was the prime factorization which worried me :-) I think all irrp are
detectable with an appropriate substitution, the question then is - which
one? (looks like knapsack to me :-( :-)

> > > 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.

Neat idea! Yep, I'll have 2 of them :-)

<more later>

njh
Received on Wed Sep 08 1999 - 00:47:05 CDT