{"id":1017,"date":"2021-04-22T14:22:26","date_gmt":"2021-04-22T14:22:26","guid":{"rendered":"https:\/\/konrad.burnik.org\/wordpress\/?p=1017"},"modified":"2023-04-27T19:59:14","modified_gmt":"2023-04-27T19:59:14","slug":"faster-complex-matrix-multiplication-via-split-complex-numbers","status":"publish","type":"post","link":"https:\/\/konrad.burnik.org\/wordpress\/faster-complex-matrix-multiplication-via-split-complex-numbers\/","title":{"rendered":"Faster Complex Matrix Multiplication via Split-Complex Numbers"},"content":{"rendered":"\n

<\/p>\n\n\n\n

Here is a nice application of split-complex numbers<\/a>. Let \"Z_1 = A + i B\" and \"Z_2 = C + i D\" be complex matrices. Their product is defined as<\/p>\n\n\n\n

  <\/span>   <\/span>\"\[ Z_1 Z_2 = (A + i B) (C + iD) = (A C - B D) + i(AD + BC) \]\"<\/p><\/p>\n\n\n\n

which requires 4 real matrix multiplications. Here I will show that we can do this with 3 real matrix multiplications by using split-complex numbers.<\/p>\n\n\n\n

First, by taking split-complex matrices \"W_1 = A + j B\" and \"W_2 = C + j D\" and rewriting them in basis \"\{\iota, \iota^*\}\" as follows <\/p>\n\n\n\n

  <\/span>   <\/span>\"\begin{align*}W_1 & = (A+B) \iota + (A-B) \iota^* \\W_2 &= (C+D) \iota + (C-D) \iota^*\end{align*}\"<\/p><\/p>\n\n\n\n

we have<\/p>\n\n\n\n

  <\/span>   <\/span>\"\[ W_1 W_2 = (A+B)(C+D) \iota + (A-B)(C-D) \iota^* \]\"<\/p><\/p>\n\n\n\n

which requires only 2 real matrix multiplications. This all follows from my previous post<\/a>.<\/p>\n\n\n\n

Let us now define

  <\/span>   <\/span>\"\begin{align*}X & := \frac{1}{2} (A + B) (C + D) \\ Y & := \frac{1}{2} (A - B) (C - D).\end{align*}\"<\/p><\/p>\n\n\n\n

We have

  <\/span>   <\/span>\"\[ W_1 W_2 = (X + Y ) + j (X - Y). \]\"<\/p><\/p>\n\n\n\n

But now, since<\/p>\n\n\n\n

  <\/span>   <\/span>\"\[ W_1 W_2 = (AC + BD) + j (AD + BC) \]\"<\/p> then by comparison \"AC + BD = X + Y\" and \"AD + BC = X - Y\".<\/p>\n\n\n\n

Finally, from this and the fact \"AC - BD = X + Y - 2 BD\" we have <\/p>\n\n\n\n

  <\/span>   <\/span>\"\[Z_1 Z_2 = (X + Y - 2 BD) + i(X - Y)\]\"<\/p> which requires only 3 real matrix multiplications, namely \"(A+B)(C+D)\", \"(A-B)(C-D)\" and \"BD\".<\/p>\n\n\n\n

EDIT: A simple implementation of this approach can be found here<\/a>.<\/em><\/p>\n

0<\/span><\/a><\/div> <\/div>
<\/div><\/div>
<\/div>","protected":false},"excerpt":{"rendered":"

Here is a nice application of split-complex numbers. Let and be complex matrices. Their product is defined as     which requires 4 real matrix multiplications. Here I will show that we can do this with 3 real matrix multiplications by using split-complex numbers. First, by taking split-complex matrices and and rewriting them in basis […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_mi_skip_tracking":false,"_exactmetrics_sitenote_active":false,"_exactmetrics_sitenote_note":"","_exactmetrics_sitenote_category":0,"_s2mail":"yes","footnotes":""},"categories":[9],"tags":[],"class_list":["post-1017","post","type-post","status-publish","format-standard","hentry","category-hyperbolic-numbers"],"_links":{"self":[{"href":"https:\/\/konrad.burnik.org\/wordpress\/wp-json\/wp\/v2\/posts\/1017","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/konrad.burnik.org\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/konrad.burnik.org\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/konrad.burnik.org\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/konrad.burnik.org\/wordpress\/wp-json\/wp\/v2\/comments?post=1017"}],"version-history":[{"count":51,"href":"https:\/\/konrad.burnik.org\/wordpress\/wp-json\/wp\/v2\/posts\/1017\/revisions"}],"predecessor-version":[{"id":1241,"href":"https:\/\/konrad.burnik.org\/wordpress\/wp-json\/wp\/v2\/posts\/1017\/revisions\/1241"}],"wp:attachment":[{"href":"https:\/\/konrad.burnik.org\/wordpress\/wp-json\/wp\/v2\/media?parent=1017"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/konrad.burnik.org\/wordpress\/wp-json\/wp\/v2\/categories?post=1017"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/konrad.burnik.org\/wordpress\/wp-json\/wp\/v2\/tags?post=1017"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}