From: <njh_at_cs.monash.edu.au>

Date: Wed, 8 Sep 1999 17:44:10 +1000 (EST)

Date: Wed, 8 Sep 1999 17:44:10 +1000 (EST)

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

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