Slow Hermite form when transformation matrix is sought.

[emmanuelthome]

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 ])

Component: linear algebra

Keywords: sd51

Reviewer: Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/11689

[loefflerd]

comment:2

The example given above works for me in 5.11.beta3 (it takes 0.08 sec). I propose to close this as fixed.

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

comment:3

Same:

sage: %time m.hermite_form(transformation=True)     
CPU times: user 0.05 s, sys: 0.00 s, total: 0.05 s
Wall time: 0.05 s
(
[1 0 0 0 1 0 1]  [      0       1       9       0  746268  284548 -486405 -344427     -18 -344412 -688859 1033287]
[0 1 0 0 1 0 0]  [      0       0      20       9  452518  172528 -294938 -208853     -40 -208812 -417677  626530]
[0 0 1 0 0 0 0]  [      0       3      17       0  689324  262819 -449293 -318141     -33 -318114 -636294  954435]
[0 0 0 2 0 0 0]  [      0       0      14       1  479869  182957 -312773 -221474     -28 -221446 -442946  664420]
[0 0 0 0 2 0 0]  [      0       5      10       0  691056  263491 -450419 -318940     -20 -318930 -637900  956840]
[0 0 0 0 0 1 1]  [      0       4       3       3  444427  169465 -289665 -205116      -6 -205118 -410239  615355]
[0 0 0 0 0 0 2]  [      0       5       8       7  523029  199433 -340893 -241393     -16 -241387 -482785  724178]
[0 0 0 0 0 0 0]  [      1       2       9       9  563288  214787 -367130 -259979     -18 -259963 -519937  779914]
[0 0 0 0 0 0 0]  [      0       6      12       4  730177  278410 -475913 -336996     -24 -336984 -674004 1011000]
[0 0 0 0 0 0 0]  [      0       0      21       6   10356    3917   -6751   -4776     -42   -4734   -9534   14310]
[0 0 0 0 0 0 0]  [      0       0       0      10  142665   54415  -92973  -65850       0  -65850 -131670  197520]
[0 0 0 0 0 0 0], [      0       0       0       0  780780  297726 -508895 -360360       0 -360360 -720720 1081080]
)

[loefflerd]

Changed keywords from none to sd51

[emmanuelthome]

comment:5

Cool. Thanks.