Wikipedia:Reference desk/Archives/Mathematics/2016 December 20
Mathematics desk | ||
---|---|---|
< December 19 | << Nov | December | Jan >> | Current desk > |
Welcome to the Wikipedia Mathematics Reference Desk Archives |
---|
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages. |
December 20
editPower of a sparse matrix
editLet be an matrix, with entries , and zero elsewhere. I wish to compute the st (last) row of , and I don't care about the other rows. Is there a fast way (faster than naive matrix multiplication or exponentiation by squaring) to compute this? 24.255.17.182 (talk) 23:05, 20 December 2016 (UTC)
- Often it is convenient to diagonalize (or put in Jordan form), then raise to powers, then un-diagonalize. I have not considered whether this is nice for your example. --JBL (talk) 23:53, 20 December 2016 (UTC)
- I don't think so- I can show that the characteristic polynomial is which doesn't factorize to anything nice in general. 24.255.17.182 (talk) 00:52, 21 December 2016 (UTC)
- You might try working out by hand a few simple examples (small n, and several small values of k) and form a hypothesis about the desired row. If the hypothesis is simple enough, it just might be easy to prove by induction. Loraof (talk) 00:19, 21 December 2016 (UTC)
- You may already know this, but depending on and , iterated multiplication could be faster than exponentiation by squaring. Right-multiplying a row vector by A requires only a left shift, two additions, and a cyclic permutation which can be handled as a renumbering of entries. Repeating this times takes time and space (assuming , ignoring factors of , and considering that the integers grow exponentially with ). Exponentiation by squaring with FFT integer multiplication and matrix multiplication would take time and space, I think. Iterated multiplication also has a smaller constant factor not only because of the simple algorithm but also because of better locality of reference. -- BenRG (talk) 20:18, 23 December 2016 (UTC)