10

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

Community
  • 1
Turbo
  • 12,812
  • 1
  • 19
  • 68

2 Answers2

4

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.

Community
  • 1
Jeff Burdges
  • 1,216
  • 6
  • 11
  • 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)? – Turbo Jan 07 '12 at 02:55
  • Yes, I should've said O(n) obviously, really O(n log n) for large n. – Jeff Burdges Jan 07 '12 at 04:35
  • Hi Jeff: Do you have a reference? – Turbo Jan 07 '12 at 05:27
  • 7
    @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). – Jeffε Jan 07 '12 at 18:44
  • I don't see a $O(n)$ formula referenced by Wikipedia. At best it looks $\Theta(n^2)$. – Peter Taylor Mar 05 '12 at 14:25
3

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.

Community
  • 1
Juan Bermejo Vega
  • 1,405
  • 1
  • 14
  • 30
  • 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$. – Turbo Mar 04 '12 at 20:13
  • That's fine, since you can compute the totient function of $3^k$ :) – Juan Bermejo Vega Mar 04 '12 at 20:34
  • well that does not simplify the complexity, I would say since the field is very very large. – Turbo Mar 04 '12 at 20:35
  • 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. – Juan Bermejo Vega Mar 04 '12 at 21:22
  • 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. – Turbo Mar 05 '12 at 05:13
  • It seems not as easy as in the Vandermonde case. I gathered some new information which might be helpful. I will update my answer. – Juan Bermejo Vega Mar 05 '12 at 12:43
  • I think something is missing in your comments A=B=I will give M-AMB=0. – Turbo Mar 05 '12 at 23:23
  • That case is not useful for the method used in the book, but I agree, I was not very clear. I corrected that and added a second reference about these displacement operator methods which may help. You may take a look now to see if the techniques are applicable. – Juan Bermejo Vega Mar 06 '12 at 00:54