1
$\begingroup$

Given matrix $M\in\Bbb F_q^{n\times n}$ with rank $r$ what is the complexity of converting to row-echelon form?

Is it $O(n^3\log q)$ or $O(n^3q)$ bit operations?

Technically $O(n^3)$ row operations in $O(\log q)$ bit words should be $O(n^3(\log q)(\log\log q)^2)$ bit operations in worst case when $q$ is prime.

What I am confused about is

  1. when $q$ is prime power

  2. incorporating complexity of modular operations.

$\endgroup$
  • $\begingroup$ When $q$ is prime, arithmetic in $\mathbb{F}_q$ is the same as arithmetic modulo $q$, and takes polylogarithmic time in $q$ (the exact running time depends on the cost of multiplication, which is $\tilde{O}(\log q)$). $\endgroup$ – Yuval Filmus Sep 25 '17 at 15:32
  • $\begingroup$ @YuvalFilmus Oh I see. So with Strassen-Schonage-Furer type integer multiplication we get $O(n^3(\log q)(\log\log q)^2)$ in worst case? $\endgroup$ – Turbo Sep 25 '17 at 18:04
1
$\begingroup$

The dependence on the field is via the cost of arithmetic operations over the field. Since numbers in $\mathbb{F}_q$ have bit size $O(\log q)$, the cost of each individual operation is polylogarithmic in $q$.

$\endgroup$
  • $\begingroup$ Is it t $O(n^3(\log q)(\log\log q)^2)$ in worst case? $\endgroup$ – Turbo Sep 25 '17 at 18:07
  • $\begingroup$ That's certainly a plausible upper bound. I think now I have given you enough information to solve your question on your own. $\endgroup$ – Yuval Filmus Sep 25 '17 at 18:08
  • $\begingroup$ $O(n^3)$ row operations in $O(\log q)$ bit words should be $O(n^3(\log q)(\log\log q)^2)$ in worst case. What I am confused about is for the case $q$ is prime power and complexity of modular operations. $\endgroup$ – Turbo Sep 25 '17 at 18:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.