Matrix

Правка en23, от DanAlex, 2015-10-25 02:31:14

Yeah, yeah, I know you expect from me matrix jokes. What if I told you I have no jokes on that ? So, just take the blue pill and go into serious stuff like ...

Cutting to the chase

I personally find matrix multiplication as the guy who sells stolen phones at the corner of the street. I mean, you get stuff at lower price but it can break in two days and you can get busted by the cops. Or not. I really need to find better metaphors...

Matrix multiplication is a well known method. People wrote on it before quite good articles, but I think you might get stuff simpler just by looking over some problems. For the ones who are familiar with the topic, you can skip to the last two problems.

Getting high fast

Now I need to find better subtitles... However, first of all to know logarithmic matrix multiplication, you have to know logarithmic multiplication.

Basically we have to compute xn considering the multiplication operation take O(1) time. Take it straight forward we get xn = x * x * .. * x , so O(N). Let's try to reduce it step by step. Let's take xn = x2 * x2 * .... And we multiply by x if n is odd. This should work fine and the constant is reduced at half. Right... Similarly we can go to xn = xsqrt(n) * xsqrt(n) * ... and this goes to O(sqrtN). This reasoning stops here.

To get it faster you have to simply observe that xn = xn / 2 * xn / 2 for n even and xn = xn / 2 * xn / 2 * x for n odd. The two terms are the same and the third is constant, so we really need to compute xn / 2 once. And xn / 4 once. And so on. Therefore the O(logN) complexity.

Now, notice that we did not specified that x is an integer or a number. The same rules hold for other mathematical associative structures such as matrices.

If you sayin' Y U NO REMEMBER MATRIX, then let me refresh your maths knowledge. You don't really need to know much about matrices to use put recurrences in a matrix multiplication form. Multiplying squared matrices is straight forward. Given two matrices their product is

$ M * N = \begin{bmatrix} a_1 & a_2 \ a_3 & a_4 \end{bmatrix} * \begin{bmatrix} b_1 & b_2 \ b_3 & b_4 \end{bmatrix} = \begin{bmatrix} a_1 * b_1 + a_2 * b_3 & a_1 * b_2 + a_2 * b_4 \ a_3 * b_1 + a_4 * b_3 & a_3 * b_2 + a_4 * b_4 \end{bmatrix} $

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en83 Английский DanAlex 2016-03-08 03:35:36 59 Tiny change: ' & ... & 0\\ 0 && 0 & ... ' -
en82 Английский DanAlex 2016-03-08 03:24:58 2 Tiny change: '= D_{n-1,k} $\n\nThe' -> '= D_{n-1,k-1} $\n\nThe'
en81 Английский DanAlex 2016-02-07 15:39:28 6 Tiny change: ' problems.\n\n### Ge' -> ' problems. [cut]\n\n### Ge'
en80 Английский DanAlex 2016-01-25 16:52:59 2 Tiny change: 't = out * x;\n retur' -> 't = out * m;\n retur'
en79 Английский DanAlex 2015-10-27 01:46:23 8
en78 Английский DanAlex 2015-10-27 01:45:38 4 Tiny change: '`==` and `&&` are bric' -> '`==` and `oo` are bric'
en77 Английский DanAlex 2015-10-27 01:45:03 559
en76 Английский DanAlex 2015-10-25 16:59:30 0 (published)
en75 Английский DanAlex 2015-10-25 16:54:33 748
en74 Английский DanAlex 2015-10-25 16:45:17 427
en73 Английский DanAlex 2015-10-25 16:41:18 31
en72 Английский DanAlex 2015-10-25 16:40:30 1120
en71 Английский DanAlex 2015-10-25 16:22:13 1 Tiny change: '-+ \n~~~~~' -> '-+ \n~~~~'
en70 Английский DanAlex 2015-10-25 16:21:53 797
en69 Английский DanAlex 2015-10-25 16:08:48 706
en68 Английский DanAlex 2015-10-25 15:57:10 66
en67 Английский DanAlex 2015-10-25 15:55:47 97
en66 Английский DanAlex 2015-10-25 15:54:38 8
en65 Английский DanAlex 2015-10-25 15:53:27 18
en64 Английский DanAlex 2015-10-25 15:52:45 7
en63 Английский DanAlex 2015-10-25 15:52:11 2 Tiny change: '. & 0 \\ ... \\ 0 & 0' -> '. & 0 \\ .&.&. \\ 0 & 0'
en62 Английский DanAlex 2015-10-25 15:51:21 376
en61 Английский DanAlex 2015-10-25 15:46:52 32
en60 Английский DanAlex 2015-10-25 15:45:55 20
en59 Английский DanAlex 2015-10-25 15:45:10 191
en58 Английский DanAlex 2015-10-25 15:43:23 12 Tiny change: 'here. ( $n<=10^9 , k <= 40$ )\n\' -> 'here. ( $n \le 10^9 , k \le 40$ )\n\'
en57 Английский DanAlex 2015-10-25 15:42:56 36
en56 Английский DanAlex 2015-10-25 15:42:01 76
en55 Английский DanAlex 2015-10-25 15:39:58 6 Tiny change: 'm. Denote `D_{(n,k)}' = number ' -> 'm. Denote $D_{n,k}$ = number '
en54 Английский DanAlex 2015-10-25 15:39:35 15
en53 Английский DanAlex 2015-10-25 15:38:28 143
en52 Английский DanAlex 2015-10-25 15:35:40 5
en51 Английский DanAlex 2015-10-25 15:35:21 452
en50 Английский DanAlex 2015-10-25 03:19:21 119
en49 Английский DanAlex 2015-10-25 03:18:05 4 Tiny change: 'matrix} ^ (n-2) = \begin{' -> 'matrix} ^ {n-2} = \begin{'
en48 Английский DanAlex 2015-10-25 03:17:48 182
en47 Английский DanAlex 2015-10-25 03:16:40 206
en46 Английский DanAlex 2015-10-25 03:14:12 7 Tiny change: 'matrix} 0 1 & 1 1 \end{bm' -> 'matrix} 0 & 1 \\ 1 & 1 \end{bm'
en45 Английский DanAlex 2015-10-25 03:13:45 258
en44 Английский DanAlex 2015-10-25 03:10:44 10
en43 Английский DanAlex 2015-10-25 03:10:10 347
en42 Английский DanAlex 2015-10-25 03:06:27 156
en41 Английский DanAlex 2015-10-25 03:01:27 37 Tiny change: 'more clear.' -> 'more clear due to the clarity of the recurrence.'
en40 Английский DanAlex 2015-10-25 03:00:37 186
en39 Английский DanAlex 2015-10-25 02:58:28 7 Tiny change: ' c;\n }\n};\n~~~~' -> ' c;\n }\n ...\n};\n~~~~'
en38 Английский DanAlex 2015-10-25 02:58:09 571
en37 Английский DanAlex 2015-10-25 02:53:18 584
en36 Английский DanAlex 2015-10-25 02:45:49 44
en35 Английский DanAlex 2015-10-25 02:44:10 23
en34 Английский DanAlex 2015-10-25 02:42:28 257
en33 Английский DanAlex 2015-10-25 02:36:49 8 Tiny change: 'ix} b_1 & b_2 \\ b_3 & b_4 \en' -> 'ix} b_1 & | & b_2 \\ b_3 & | & b_4 \en'
en32 Английский DanAlex 2015-10-25 02:36:17 5 Tiny change: '& a_2 \\ ---- \\ a_3 &' -> '& a_2 \\ - & - \\ a_3 &'
en31 Английский DanAlex 2015-10-25 02:35:58 3 Tiny change: '& a_2 \\ - - \\ a_3 &' -> '& a_2 \\ ---- \\ a_3 &'
en30 Английский DanAlex 2015-10-25 02:35:41 4 Tiny change: '& a_2 \\ ----- \\ a_3 &' -> '& a_2 \\ - - \\ a_3 &'
en29 Английский DanAlex 2015-10-25 02:35:24 9 Tiny change: ' & a_2 \\ a_3 & ' -> ' & a_2 \\ ----- \\ a_3 & '
en28 Английский DanAlex 2015-10-25 02:34:35 7 Tiny change: '{bmatrix} $ = \n$\begin{bma' -> '{bmatrix} = \begin{bma'
en27 Английский DanAlex 2015-10-25 02:34:14 4
en26 Английский DanAlex 2015-10-25 02:33:38 18
en25 Английский DanAlex 2015-10-25 02:32:46 5 Tiny change: '{bmatrix} = \n\begin{b' -> '{bmatrix} $ = $\n\begin{b'
en24 Английский DanAlex 2015-10-25 02:32:15 76
en23 Английский DanAlex 2015-10-25 02:31:14 68
en22 Английский DanAlex 2015-10-25 02:30:11 217
en21 Английский DanAlex 2015-10-25 02:27:25 43
en20 Английский DanAlex 2015-10-25 02:26:39 4
en19 Английский DanAlex 2015-10-25 02:25:45 11
en18 Английский DanAlex 2015-10-25 02:24:46 7
en17 Английский DanAlex 2015-10-25 02:24:31 3
en16 Английский DanAlex 2015-10-25 02:24:09 4
en15 Английский DanAlex 2015-10-25 02:23:44 20
en14 Английский DanAlex 2015-10-25 02:22:34 75
en13 Английский DanAlex 2015-10-25 02:20:26 7
en12 Английский DanAlex 2015-10-25 02:20:08 45
en11 Английский DanAlex 2015-10-25 02:19:17 54
en10 Английский DanAlex 2015-10-25 02:17:40 73
en9 Английский DanAlex 2015-10-25 02:15:46 1 Tiny change: ' \n\n$M = \[a & b & c' -> ' \n\n$M = [a & b & c'
en8 Английский DanAlex 2015-10-25 02:15:30 56
en7 Английский DanAlex 2015-10-25 02:14:55 95
en6 Английский DanAlex 2015-10-25 02:11:32 478
en5 Английский DanAlex 2015-10-25 02:02:29 333
en4 Английский DanAlex 2015-10-25 01:57:53 6 Tiny change: ' = x^{sqrt n} * x^{sqrt n} * ...$ a' -> ' = x^{sqrt(n)} * x^{sqrt(n)} * ...$ a'
en3 Английский DanAlex 2015-10-25 01:57:35 10
en2 Английский DanAlex 2015-10-25 01:56:21 268
en1 Английский DanAlex 2015-10-25 01:53:13 1004 Initial revision (saved to drafts)