#12103: Use MeatAxe as an optional back end for dense matrices over `GF(p^n)`, p
odd, n>1, `p^n<255`
-------------------------------------+-------------------------------------
Reporter: SimonKing | Owner: jason, was
Type: defect | Status: needs_work
Priority: major | Milestone: sage-6.4
Component: packages: | Resolution:
experimental | Merged in:
Keywords: linear algebra, | Reviewers:
MeatAxe | Work issues:
Authors: Simon King | Commit:
Report Upstream: None of the above | c1d5026ade5e1bb454401a34a734c91c15cbf75f
- read trac for reasoning. | Stopgaps:
Branch: |
u/SimonKing/meataxe |
Dependencies: |
-------------------------------------+-------------------------------------
Comment (by SimonKing):
Just to see if I can improve the code a bit, I did
{{{
sage: M = MatrixSpace(GF(125,'x'),2000).random_element()
sage: %crun N = M*M
PROFILE: interrupts/evictions/bytes = 1466/1183/718104
Using local file /home/king/Sage/git/sage/local/bin/python.
Using local file /home/king/.sage/temp/linux-
va3e.site/18759/tmp_efM3tZ.perf.
Total: 1466 samples
0 0.0% 0.0% 1466 100.0% MatMulStrassen
0 0.0% 0.0% 1466 100.0% PyEval_EvalCode
0 0.0% 0.0% 1466 100.0% PyEval_EvalCodeEx
0 0.0% 0.0% 1466 100.0% PyEval_EvalFrameEx
0 0.0% 0.0% 1466 100.0% PyNumber_Multiply
0 0.0% 0.0% 1466 100.0% PyObject_Call
0 0.0% 0.0% 1466 100.0% PyRun_FileExFlags
0 0.0% 0.0% 1466 100.0% PyRun_SimpleFileExFlags
0 0.0% 0.0% 1466 100.0% PyRun_StringFlags
0 0.0% 0.0% 1466 100.0% Py_Main
0 0.0% 0.0% 1466 100.0% StrassenStep
0 0.0% 0.0% 1466 100.0% __libc_start_main
0 0.0% 0.0% 1466 100.0%
__pyx_f_4sage_6matrix_17matrix_gfpn_dense_17Matrix_gfpn_dense__matrix_times_matrix_
0 0.0% 0.0% 1466 100.0%
__pyx_f_4sage_6matrix_17matrix_gfpn_dense_17Matrix_gfpn_dense__multiply_strassen
0 0.0% 0.0% 1466 100.0%
__pyx_pf_4sage_9structure_7element_6Matrix_2__mul__ (inline)
0 0.0% 0.0% 1466 100.0%
__pyx_pw_4sage_9structure_7element_6Matrix_3__mul__
0 0.0% 0.0% 1466 100.0% _start
0 0.0% 0.0% 1466 100.0% binary_op1 (inline)
0 0.0% 0.0% 1466 100.0% call_function (inline)
0 0.0% 0.0% 1466 100.0% exec_statement (inline)
0 0.0% 0.0% 1466 100.0% ext_do_call (inline)
0 0.0% 0.0% 1466 100.0% fast_function (inline)
0 0.0% 0.0% 1466 100.0% function_call
0 0.0% 0.0% 1466 100.0% run_mod (inline)
2 0.1% 0.1% 1382 94.3% WindowAddMul
1368 93.3% 93.5% 1368 93.3% FfAddMapRowWindow
0 0.0% 93.5% 46 3.1% WindowDif
2 0.1% 93.6% 31 2.1% WindowSum
30 2.0% 95.6% 30 2.0% FfSetNoc
23 1.6% 97.2% 23 1.6% FfAddRowPartial
23 1.6% 98.8% 23 1.6% FfSubRowPartial
8 0.5% 99.3% 8 0.5% FfSubRowPartialReverse
0 0.0% 99.3% 4 0.3% WindowClear
4 0.3% 99.6% 4 0.3% __GI_memset
0 0.0% 99.6% 3 0.2% FfAlloc
0 0.0% 99.6% 3 0.2% MatAlloc
0 0.0% 99.6% 3 0.2% WindowAlloc
2 0.1% 99.7% 2 0.1% FfStepPtr
0 0.0% 99.7% 2 0.1% SysMalloc
1 0.1% 99.8% 2 0.1% __GI___libc_malloc
0 0.0% 99.8% 1 0.1% FfAddRow
0 0.0% 99.8% 1 0.1% FfGetPtr
1 0.1% 99.9% 1 0.1% FfMulRow
1 0.1% 99.9% 1 0.1% __memcpy_sse2_unaligned
0 0.0% 99.9% 1 0.1% _int_malloc
1 0.1% 100.0% 1 0.1% malloc_consolidate
sage: %crun N = M._multiply_classical(M)
PROFILE: interrupts/evictions/bytes = 2242/24/17464
Using local file /home/king/Sage/git/sage/local/bin/python.
Using local file /home/king/.sage/temp/linux-
va3e.site/18759/tmp_R9Qzph.perf.
Total: 2242 samples
0 0.0% 0.0% 2242 100.0% PyEval_EvalCode
0 0.0% 0.0% 2242 100.0% PyEval_EvalCodeEx
0 0.0% 0.0% 2242 100.0% PyEval_EvalFrameEx
0 0.0% 0.0% 2242 100.0% PyObject_Call
0 0.0% 0.0% 2242 100.0% PyRun_FileExFlags
0 0.0% 0.0% 2242 100.0% PyRun_SimpleFileExFlags
0 0.0% 0.0% 2242 100.0% PyRun_StringFlags
0 0.0% 0.0% 2242 100.0% Py_Main
0 0.0% 0.0% 2242 100.0% __libc_start_main
0 0.0% 0.0% 2242 100.0%
__pyx_f_4sage_6matrix_17matrix_gfpn_dense_17Matrix_gfpn_dense__multiply_classical
0 0.0% 0.0% 2242 100.0%
__pyx_pf_4sage_6matrix_17matrix_gfpn_dense_17Matrix_gfpn_dense_32_multiply_classical
(inline)
0 0.0% 0.0% 2242 100.0%
__pyx_pw_4sage_6matrix_17matrix_gfpn_dense_17Matrix_gfpn_dense_33_multiply_classical
0 0.0% 0.0% 2242 100.0% _start
0 0.0% 0.0% 2242 100.0% call_function (inline)
0 0.0% 0.0% 2242 100.0% exec_statement (inline)
0 0.0% 0.0% 2242 100.0% ext_do_call (inline)
0 0.0% 0.0% 2242 100.0% fast_function (inline)
0 0.0% 0.0% 2242 100.0% function_call
0 0.0% 0.0% 2242 100.0% run_mod (inline)
2241 100.0% 100.0% 2241 100.0% FfMapRow
0 0.0% 100.0% 2241 100.0% MatMul
0 0.0% 100.0% 1 0.0% FfAlloc
1 0.0% 100.0% 1 0.0% FfMulRow
0 0.0% 100.0% 1 0.0% MatAlloc
0 0.0% 100.0% 1 0.0% MatDup
}}}
So, if I want to optimise something then I should have a look at
`FfMapRow/FfAddMapRowWindow`.
--
Ticket URL: <http://trac.sagemath.org/ticket/12103#comment:96>
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.
