#11689: Slow Hermite form when transformation matrix is sought.
---------------------------+-----------------------------------------------
Reporter: thome | Owner: jason, was
Type: | Status: positive_review
enhancement | Milestone: sage-duplicate/invalid/wontfix
Priority: major | Resolution:
Component: linear | Merged in:
algebra | Reviewers: Travis Scrimshaw
Keywords: sd51 | Work issues:
Authors: | Dependencies:
Report Upstream: N/A |
Branch: |
Stopgaps: |
---------------------------+-----------------------------------------------
Changes (by davidloeffler):
* keywords: => sd51
Old description:
> Here is a small example which does not seem to complete for computing the
> transformation matrix for a HNF computation. This is using sage-4.7 on a
> core2 linux laptop:
>
> {{{
> sage: m=matrix([[2, 0, 0, 0, 0, 0, 0],
> [0, 2, 0, 0, 0, 0, 0],
> [0, 0, 2, 0, 0, 0, 0],
> [0, 0, 0, 6, 0, 0, 0],
> [0, 0, 0, 0, 12, 0, 0],
> [0, 0, 0, 0, 0, 420, 0],
> [0, 0, 0, 0, 0, 0, 360360],
> [1, 0, 0, 2, 11, 395, 81308],
> [0, 1, 1, 4, 11, 45, 18485],
> [0, 1, 0, 4, 7, 396, 173226],
> [1, 1, 0, 0, 4, 9, 64882],
> [1, 1, 0, 2, 0, 154, 297731]])
> sage: time m.hermite_form(transformation=True)
> }}}
>
> The HNF without the transformation matrix is trivial to compute, clearly.
>
> For the record, here is the transformation matrix (which magma computes
> in no time):
>
> {{{
> sage: tt=matrix(12,12,[ 1276791278917091409, 1276791235190372179,
> -43726719228, -58302458417, 851194105779241797, 54719616869120608,
> 459766738541193814, 0, 87453438456, 3, -2553582557834681150, 498333,
> 425640651405808007, 425640636828743170, -14577064837, -19436141826,
> 283760407545975179, 18241739079391952, 153271264707710346, 0,
> 29154129674, 1, -851281302811782142, 166128, -1276729789968218301,
> -1276729746243604905, 43724613395, 58299650631, -851153113150520412,
> -54716981628905876, -459744596650074623, 0, -87449226789, -3,
> 2553459579936934911, -498309, -1635126640, -1635126584, 56, 75,
> -1090084324, -70076844, -588801674, 0, -112, 0, 3270253280, 0,
> 851127575827561834, 851127546678696901, -29148864932, -38865263976,
> 567418330445566245, 36476889860595476, 306487173026908773, 0,
> 58297729864, 2, -1702255151655455864, 332196, -851109637009591746,
> -851109607861341170, 29148250575, 38864444831, -567406371234712505,
> -36476121054242694, -306480713340061298, 0, -58296501150, -2,
> 1702219274019515681, -332189, -851158317562466579, -851158288412548823,
> 29149917755, 38866667744, -567438824933572570, -36478207363294356,
> -306498242985975411, 0, -58299835510, -2, 1702316635125265366, -332208,
> 34765116772769516885755, 34765115582156356215338, -1190613160629573,
> -1587488737181287, 23176742332393406342697, 1489933320839760309322,
> 12518760597406858504121, 1, 2381226321259146, 81689,
> -69530233545552602633701, 13568862190, 2553459579936436602,
> 2553459492487209810, -87449226789, -116599301262, 1702306226301040824,
> 109433963257811752, 919489193300149246, 0, 174898453578, 6,
> -5106919159873869822, 996618, 153726984054180, 153726978789438, -5264742,
> -7019676, 102484646384113, 6588298188428, 55356388511919, 0, 10529484, 0,
> -307453968108420, 60, 2452689960, 2452689876, -84, -112, 1635126486,
> 105115266, 883202511, 0, 168, 0, -4905379920, 0, -90090, -90090, 0, 0,
> -60060, -3861, -32441, 0, 0, 0, 180180, 0 ])
> }}}
New description:
Here is a small example which does not seem to complete for computing the
transformation matrix for a HNF computation. This is using sage-4.7 on a
core2 linux laptop:
{{{
sage: m=matrix([[2, 0, 0, 0, 0, 0, 0],
[0, 2, 0, 0, 0, 0, 0],
[0, 0, 2, 0, 0, 0, 0],
[0, 0, 0, 6, 0, 0, 0],
[0, 0, 0, 0, 12, 0, 0],
[0, 0, 0, 0, 0, 420, 0],
[0, 0, 0, 0, 0, 0, 360360],
[1, 0, 0, 2, 11, 395, 81308],
[0, 1, 1, 4, 11, 45, 18485],
[0, 1, 0, 4, 7, 396, 173226],
[1, 1, 0, 0, 4, 9, 64882],
[1, 1, 0, 2, 0, 154, 297731]])
sage: time m.hermite_form(transformation=True)
}}}
The HNF without the transformation matrix is trivial to compute, clearly.
For the record, here is the transformation matrix (which magma computes in
no time):
{{{
sage: tt=matrix(12,12,[ 1276791278917091409, 1276791235190372179,
-43726719228, -58302458417, 851194105779241797, 54719616869120608,
459766738541193814, 0, 87453438456, 3, -2553582557834681150, 498333,
425640651405808007, 425640636828743170, -14577064837, -19436141826,
283760407545975179, 18241739079391952, 153271264707710346, 0, 29154129674,
1, -851281302811782142, 166128, -1276729789968218301,
-1276729746243604905, 43724613395, 58299650631, -851153113150520412,
-54716981628905876, -459744596650074623, 0, -87449226789, -3,
2553459579936934911, -498309, -1635126640, -1635126584, 56, 75,
-1090084324, -70076844, -588801674, 0, -112, 0, 3270253280, 0,
851127575827561834, 851127546678696901, -29148864932, -38865263976,
567418330445566245, 36476889860595476, 306487173026908773, 0, 58297729864,
2, -1702255151655455864, 332196, -851109637009591746, -851109607861341170,
29148250575, 38864444831, -567406371234712505, -36476121054242694,
-306480713340061298, 0, -58296501150, -2, 1702219274019515681, -332189,
-851158317562466579, -851158288412548823, 29149917755, 38866667744,
-567438824933572570, -36478207363294356, -306498242985975411, 0,
-58299835510, -2, 1702316635125265366, -332208, 34765116772769516885755,
34765115582156356215338, -1190613160629573, -1587488737181287,
23176742332393406342697, 1489933320839760309322, 12518760597406858504121,
1, 2381226321259146, 81689, -69530233545552602633701, 13568862190,
2553459579936436602, 2553459492487209810, -87449226789, -116599301262,
1702306226301040824, 109433963257811752, 919489193300149246, 0,
174898453578, 6, -5106919159873869822, 996618, 153726984054180,
153726978789438, -5264742, -7019676, 102484646384113, 6588298188428,
55356388511919, 0, 10529484, 0, -307453968108420, 60, 2452689960,
2452689876, -84, -112, 1635126486, 105115266, 883202511, 0, 168, 0,
-4905379920, 0, -90090, -90090, 0, 0, -60060, -3861, -32441, 0, 0, 0,
180180, 0 ])
}}}
'''Release manager: please close as fixed.'''
--
--
Ticket URL: <http://trac.sagemath.org/ticket/11689#comment:4>
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/groups/opt_out.
