#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: Travis Scrimshaw
Authors: John Palmieri | Work issues:
Report Upstream: N/A | Commit:
Branch: u/tscrim/AT-model | 716469ac9519fc492467d4a635c80468880df94d
Dependencies: #19179 | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by tscrim):
Replying to [comment:31 jhpalmieri]:
> 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 didn't mean to imply that it wasn't a significant speedup and I
apologize if I did. However that is a much larger difference than I really
expected. Eeek!
> 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.
It sounds like #2705 will help for the sparse case, but I can dig around
in the sparse matrix code and try to find out ways I can squeeze speed out
of the matrix operations (and use hints from the tickets I cited) if you
think it's worth it for this ticket. See also my previous replay
--
Ticket URL: <http://trac.sagemath.org/ticket/6102#comment:33>
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.
