10
$\begingroup$

Moore matrix is similar to Vandermonde matrix but has a slightly modified definition. http://en.wikipedia.org/wiki/Moore_matrix

What is the complexity of computing the determinant of a given $n \times n$ full rank Moore matrix modulo some integer?

Can Moore determinant be reduced from $O(n^{3})$ using FFT techniques to $O(n\log^{a}n)$ for some $a \in \mathbb{R}_{+} \cup \{0\}$?

Is complexity of Moore det modulo an integer and Vandermonde det the same? Complexity of Vandermonde determinant is $O(n\log^{2}n)$ (Page 644 in Handbook of Theoretical Computer Science: Algorithms and complexity By Jan Leeuwen)

Post similar to the current one: Determinant modulo m

$\endgroup$
  • $\begingroup$ Can the Moore determinant even be computed in O(n^3) time (on an integer RAM)? $\endgroup$ – Jeffε Jan 7 '12 at 18:42
  • 1
    $\begingroup$ @JɛffE That is why I mentioned modulo random $N \in \mathbb{N}$. $\endgroup$ – T.... Jan 8 '12 at 0:14
  • $\begingroup$ By the way, and I'm just curious, are there known applications that would benefit of such "superfast" algorithm? $\endgroup$ – Juan Bermejo Vega Mar 6 '12 at 1:01
  • $\begingroup$ @J$\varepsilon$ffE, do you happen to know if computing a double modular exponentiation over $N$ is in BPP for trivial $N$?. Because that's a problem to compute the coefficients of the matrix. $\endgroup$ – Juan Bermejo Vega Mar 6 '12 at 1:03
4
$\begingroup$

In general, there is a theoretical $O(n^{2.376})$ time algorithm for finding the LU decomposition of an arbitrary matrix using the Coppersmith–Winograd algorithm, which then obviously yields the determinant (adding $O(n)$ time). There is a problem however that the Coppersmith–Winograd algorithm isn't considered usable in practice. Afaik, people mostly use the $O(n^{2.807})$ time Strassen algorithm. Doesn't Boost UBLAS's lu_factorize use this?

In you case, the Moore matrix should admit considerable optimizations because basically any Gaussian elimination like procedure like LU decomposition can be done abstractly. Indeed, you'll find a nice $O(n)$ formula for computing the Moore determinant referenced by wikipedia, which presumably one proves by simply working out the LU decomposition in general.

$\endgroup$
  • $\begingroup$ Hi Jeff: Which reference are you refererring for the O(n^2) formula. I think Vandermonde det can be calculated in O(nlogn) but I cannot find reference. So should Moore det also be in O(nlogn)? $\endgroup$ – T.... Jan 7 '12 at 2:55
  • $\begingroup$ Yes, I should've said O(n) obviously, really O(n log n) for large n. $\endgroup$ – Jeff Burdges Jan 7 '12 at 4:35
  • $\begingroup$ Hi Jeff: Do you have a reference? $\endgroup$ – T.... Jan 7 '12 at 5:27
  • 7
    $\begingroup$ @JeffBurdges: If the running time is O(n log n) "for large n", then by definition, the running time is O(n log n), not O(n). $\endgroup$ – Jeffε Jan 7 '12 at 18:44
  • $\begingroup$ I don't see a $O(n)$ formula referenced by Wikipedia. At best it looks $\Theta(n^2)$. $\endgroup$ – Peter Taylor Mar 5 '12 at 14:25
3
$\begingroup$

It is important that, in the definition you provide, the matrix lives in a finite field, say $\mathbb{Z}_m$ where $m$ is prime. This allows you to use Euler's theorem to compute the double-exponentials $a^{q^e}\mod m$ that appear in the matrix in time $O(\log (mn) \; M(\log m))$. $$a^{q^i}\equiv a^{q^i\pmod{\varphi(m)}}\pmod m$$ Otherwise, it seems hard even to compute the matrix coefficients without factorising $m$.

If $m$ is prime or can be efficiently factorised, the worst-case complexity is dominated by the number of steps you need for matrix multiplication $O(n^\omega)$. For instance, the Smith normal form approach I mentioned in the partner post would compute the determinant in time $O\left( n^\omega \; \log^2m\; \log (mn) \right)$ if you use "slow" multiplication algorithms$^*$. $\omega$ can be chosen to be 2.373.

You get a slow-down in Moore vs Vandermonde since you must double-exponentiate the coefficients of the matrix. When you can factorise $m$ this slow-down is just polylogarithmic on $m$. If not, the algorithm presented gives you a Cook reduction to Double-Modular-Exponentiation on $\mathbb{Z}_m$.

Note *: faster algorithms for integer multiplication allow you to replace $\log^2 m$ with $M(\log m \log\log m)$ .


Update: on the possibility of achieving $O(n\log^a n)$.

I have no definite answer for this, but I found some information that may tighten your search.

Algorithms for structured matrices that compute quantities like determinants in time $O(n\log^a n)$ are called "superfast" in the literature. All known "superfast" algorithms for structured matrices (Vandermonde, Toeplitz, Hankel) seem to rely on a common property of this matrices known as low "displacement rank". Confer the discussion on the first chapter of this book (open access pages), or in this article [ACM],[PDF].

From what I read, given a $m\times n$ Moore matrix $M$, if you were able to find matrices $A$, $B$ such that the new matrix $L(M)=AM-MB$ (or alternatively $L(M)=M- AMB$) has the following structure

$$L(M) = \sum_{k=1}^r g_k h_k^T $$

, and the rank $r>0$ is small (either constant or bounded by $o(\text{min} \;\{m,n\})$), then you can apply existing techniques (check chapter 5 of the book, open-access pages) to triangularise $M$ and, hence, compute $\det{M}$, using $O(n\log^2 n)$. Above, the $g_k$, $h_k$ denote vectors. If you can not find the book above to read the whole thing, this article has also a lot of information about these methods.

Unfortunately, I have no been able to find a low-displacement-rank structure for the Moore matrix (Vandermonde has). The main complication here seems to arise from the "non-linear" nature of the double exponential. If it helps, the cases for Vandermonde, Cauchy, Toeplitz, Hankel are worked out in the book.

$\endgroup$
  • $\begingroup$ I can make my matrix live in a field of char $3$. However, the size of alphabets for my intended application will be large. So $m$ is of form $3^{k}$ for some large enough $k$. $\endgroup$ – T.... Mar 4 '12 at 20:13
  • $\begingroup$ That's fine, since you can compute the totient function of $3^k$ :) $\endgroup$ – Juan Bermejo Vega Mar 4 '12 at 20:34
  • $\begingroup$ well that does not simplify the complexity, I would say since the field is very very large. $\endgroup$ – T.... Mar 4 '12 at 20:35
  • $\begingroup$ It does simplify the problems I mention with the double-exponentiation. Since $\varphi(3^k)=3^k-3^{k-1}$, you can use Euler's theorem to double exponentiate $a^{q^i}\mod m$: first, compute $b=q^i\mod \varphi(3^k)$, then $a^b\mod 3^k$. You can do this in time $O(\log(n3^k)M(k \log3))$. Using school-multiplication algorithm, $M(n)=n^2$, and you would get a final "netto" cost of $O(n^\omega k^2 log^2 3 (\log n + k\log 3))$ which is efficient. $\endgroup$ – Juan Bermejo Vega Mar 4 '12 at 21:22
  • $\begingroup$ Can we replace $\omega$ by $1 + \epsilon$? That is the cost saving I curious in (may be possible from the matrix structure). With $\omega \ge 2$, I don't gain anything for my purpose. $\endgroup$ – T.... Mar 5 '12 at 5:13

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.