Georgi Guninski on Sat, 08 Jan 2022 08:36:58 +0100

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Complexity of qfisom()

I read the Fine Manual, but didn't find the answer.
qfisom(G,H) returns matrix S such that G=S^T H S.

1. Must S be permutation matrix up to sign (-1 entry is possible)?
2. What is the complexity of qfisom(), under what hypothesis
the complexity is exp(o(n)) (small Oh)?

According to my tests, qfisom() is very efficient both on random
and structured instances, when I first do qi=qfisominit(G,[2,3]).

3. Is it correct to use qi=qfisominit(G,[2,3])?

Attached is example, which takes only 0.3 seconds for 100 x 100 matrices
with the [2,3] trick.

Description: application/gzip