I'm looking for some references on the complexity for the following kind of problem:

Given two Basis $(a_1, ... ,a_n)$ and $(b_1, ..., b_n)$ of the $K(x)$-vector space $V$ I want to compute the transformation matrix $M \in K(x)^{n \times n}$ which satifies the equation $$ (b_1, ..., b_n) \cdot M = (a_1, ... ,a_n).$$

Either I simply don't know the name of this kind of problem or there is another rather trivial reason that I can't find any references. There has been much effort in scientific research solving linear equations of the form $$ Ax = b $$ for given $A$ and $b$, hence I can't see any reason why not to do the same for my desired problem. Maybe there is a direct link between those tasks or any other reduction of my problem to another well known problem for which complexity analysis has been done.

Edit: An (for my case) equivalent problem is to determine the matrix $M$ such that $M$ satisfies $$ M_b \cdot M = M_a $$ where $M_a, M_b$ are representation matrices for $(a_1,...,a_n)$ and $(b_1,...b_n)$ for a fixed basis of the regarded $K(x)$ vector space. Therefore with polynomial matrix inversion I would achieve my goals, unfortunately this has time complexity $O^{\sim}(n^3 d)$ where $d$ denotes the maximal degree of the entries of the considered matrix (cf. On the Complexity of Polynomial Matrix Computations). But the complexity I'm looking for should be $O^{\sim}(n^\omega d)$.

I would appreciate any kind of help, recommendations or hint for the name of this problem. Thank you very much!

  • $\begingroup$ It seems then that you're just looking to compute the matrix product $M=M_b^{-1}M_a$, right? $\endgroup$ – Omnomnomnom Aug 30 '15 at 12:28
  • $\begingroup$ Also, are you saying that the matrices have entries in $K(x)$, or that the vector space under consideration is $K(x)$? $\endgroup$ – Omnomnomnom Aug 30 '15 at 12:35
  • 1
    $\begingroup$ Yes, it would be sufficient to be able to compute $M = M_b^{-1}M_a$, but given the matrices $M_a, M_b$, say of degree $d$, computing the inverse $M_b^{-1}$ would be too expensive, see the link in my question. The matrices are defined over $K(x)$, we consider the vector space $V$ of dimension $n$ over $K(x)$. $\endgroup$ – gisma Aug 30 '15 at 12:51
  • $\begingroup$ At the very least, we can say that computing $A^{-1}B$ is at most as bad as computing $A^{-1}b$ for $n$ columns $b$. $\endgroup$ – Omnomnomnom Aug 30 '15 at 12:57
  • $\begingroup$ There exist many good libraries for doing this kind calculation. Some important questions are: (1) how big is $n$ in the applications you are considering, (2) does $M_b$ have any special structure you can exploit, (3) is there some performance requirement you need to hit? $\endgroup$ – K. Miller Aug 30 '15 at 13:26

Your Answer

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

Browse other questions tagged or ask your own question.