#19340: Better interface for hadamard_matrix
-------------------------------------+-------------------------------------
Reporter: ncohen | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.9
Component: combinatorial | Resolution:
designs | Merged in:
Keywords: | Reviewers:
Authors: Nathann Cohen | Work issues:
Report Upstream: N/A | Commit:
Branch: u/ncohen/19340 | a5a4bbff80f2aed2a5b549d6b64f215967bc5ec7
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by dimpase):
Replying to [comment:19 fredrik.johansson]:
> Replying to [comment:18 dimpase]:
> > Replying to [comment:6 fredrik.johansson]:
> > > You might consider using the flint functions fmpz_mat_hadamard and
fmpz_mat_is_hadamard, which should be faster.
> > >
> > > Checking by default seems kind of useless since this is much slower
than generating the matrix (generating a size 1000 Hadamard matrix takes
0.01 seconds and checking it takes 0.5 seconds),
> >
> > IMHO it says that your fmpz_mat_is_hadamard is far from optimal.
> > Indeed, you neither need to take the transpose nor to do full matrix
multiplication.
> >
> > As you fisrt check that the matrix is +/-1, you don't need to check
that the diagonal entries of HH.T are all n.
> > So you only need to do scalar products of n(n-1)/2 rows...
>
> I didn't follow this. Are you saying that you can do the test in
{{{O(n^2)}}} instead of {{{O(n^omega)}}}?
No, I am not saying that you can do the scalar product of two matrix rows
in constant time. :-)
But at least you can replace
{{{
for (i = 0; i < n && result; i++)
for (j = 0; j < n && result; j++)
result = (*fmpz_mat_entry(C, i, j) == n * (i == j));
}}}
with
{{{
for (i = 0; i < n && result; i++)
for (j = i+1; j < n && result; j++)
result = (*fmpz_mat_entry(C, i, j) == 0);
}}}
another possible optimisation would be to have a dedicated function for
matrix multiplication with the symmetric result (for `HH^T` is symmetric;
other possible use would be to compute product of commuting symmetric
matrices).
--
Ticket URL: <http://trac.sagemath.org/ticket/19340#comment:20>
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.
