#6102: cohomology ring of simplicial complexes
-------------------------------------+-------------------------------------
Reporter: bantieau | Owner: bantieau
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.10
Component: algebraic | Resolution:
topology | Merged in:
Keywords: | Reviewers:
Authors: John Palmieri | Work issues:
Report Upstream: N/A | Commit:
Branch: u/jhpalmieri/AT- | 0d2ea83c0d4a66ff254e9382376b04f90d921964
model | Stopgaps:
Dependencies: #19179 |
-------------------------------------+-------------------------------------
Comment (by jhpalmieri):
Replying to [comment:30 tscrim]:
> Those are some very good improvements.
>
> I really don't like this:
> {{{#!python
> # diff is sparse and low density. Dense matrices are faster
> # over finite fields, but for low density matrices, sparse
> # matrices are faster over the rationals.
> if base_ring != QQ:
> diff = diff.dense_matrix()
> }}}
> It's not a blocker for this to get a positive review, but it bugs me.
Plus the extra time to convert it to a dense matrix...
On my computer, if I do
{{{
sage: from sage.homology.algebraic_topological_model import
algebraic_topological_model
sage: RP3 = simplicial_complexes.RealProjectiveSpace(3)
sage: %timeit algebraic_topological_model(RP3, GF(2))
}}}
then without this change, it takes 104 ms per loop; with the change it
takes 19.5 ms per loop. (Similar over `GF(31)`, to pick a random other
finite field.) So the time for converting to a dense matrix is outweighed
by the speed when multiplying dense vs. sparse matrices and vectors.
> I did some quick digging and there is apparently a slew of tickets on
improving sparse or modn vectors/matrices: #19076 (and therein), #18231,
#15104, #10312, #18312, #2705.
>
> Was there anything in your timings to suggest a good place to go look
for just using sparse matrices? Did you also test with my fixes for #19377
and #19378 (and forcing sparse matrices, or are they even necessary)?
The fixes for #19377 and #19378 won't make much of a difference, because I
think the main bottlenecks are matrix-matrix multiplication and matrix-
vector multiplication. For #19378, it's easy enough to bypass the whole
issue by testing whether the appropriate matrix is `nx0`. #18231 could
help, since at least with the Delta-complex version, some of the slowest
parts are constructing matrices.
I don't know where to look in the linear algebra code to improve the
timings. I ran tests of the form
{{{
%timeit random_matrix(QQ, 40, density=0.1, sparse=True) *
random_vector(QQ, 40, density=0.1, sparse=False)
}}}
and similarly with the second factor being a vector, and then I varied
which factors were sparse. I tried with different coefficient fields,
also. Over the rationals, as the density decreases, the timing for dense
matrices stays pretty constant, but it speeds up for sparse matrices.
(This is without even taking into account the fact that it is slower to
construct random sparse matrices: see #2705.) Over finite fields, it's
constant both ways, and slower for sparse matrices.
> Is there anything else you'd like to do to this before I set it to
positive review?
I think that cup products for Delta complexes can come on a separate
ticket, if anyone ever figures it out. I'll see what I can do, but I don't
want it to hold up this ticket.
--
Ticket URL: <http://trac.sagemath.org/ticket/6102#comment:31>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
