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$
2
  • $\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$ Sep 25, 2017 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, 2017 at 18:04

1 Answer 1

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$
3
  • $\begingroup$ Is it t $O(n^3(\log q)(\log\log q)^2)$ in worst case? $\endgroup$
    – Turbo
    Sep 25, 2017 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$ Sep 25, 2017 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, 2017 at 18:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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