{"id":1078,"date":"2021-04-24T09:13:01","date_gmt":"2021-04-24T09:13:01","guid":{"rendered":"https:\/\/konrad.burnik.org\/wordpress\/?p=1078"},"modified":"2021-04-26T18:58:02","modified_gmt":"2021-04-26T18:58:02","slug":"implementation-of-faster-complex-matrix-multiplication-via-split-complex-numbers","status":"publish","type":"post","link":"https:\/\/konrad.burnik.org\/wordpress\/implementation-of-faster-complex-matrix-multiplication-via-split-complex-numbers\/","title":{"rendered":"Implementation of Faster Complex Matrix Multiplication via Split-Complex Numbers"},"content":{"rendered":"\n

In my previous post<\/a>, I showed that split-complex numbers can be used to speed up complex matrix multiplication.<\/p>\n\n\n\n

In this post I will do a quick measurement on exactly how much faster is the new approach when compared to the naive implementation in practice. Since we are using 3 real matrix multiplications in the new approach as opposed to 4 in the naive approach we would expect up to 25% improvement in the runtime. We can easily implement and test this by using Python's NumPy library<\/a>. In the following listing the hyperbolic_matrix_mult<\/code> function is the new approach that uses split-complex numbers and complex_matrix_mult<\/code> is the function implementing the naive complex matrix multiplication.<\/p>\n\n\n\n

# matrix_mult.py\n\nimport numpy as np\n\ndef hyperbolic_matrix_mult(Z1, Z2, W1, W2):\n    X = 0.5 * (Z1 + Z2).dot(W1 + W2)\n    Y = 0.5 * (Z1 - Z2).dot(W1 - W2)\n    return X + Y - 2.0 * Z2.dot(W2), X - Y\n\ndef complex_matrix_mult(Z1, Z2, W1, W2):\n    return Z1.dot(W1) - Z2.dot(W2), Z1.dot(W2) + Z2.dot(W1)<\/pre>\n\n\n\n
I will be running the test on my MacBook laptop with the following specs:<\/p>\n\n\n\n
Hardware Overview:\n\n  Model Name:                   MacBook Pro\n  Model Identifier:             MacBookPro13,3\n  Processor Name:               Quad-Core Intel Core i7\n  Processor Speed:              2,6 GHz\n  Number of Processors:         1\n  Total Number of Cores:        4\n  L2 Cache (per Core):          256 KB\n  L3 Cache:                     6 MB\n  Hyper-Threading Technology:   Enabled\n  Memory:                       16 GB<\/pre>\n\n\n\n
The test will be as follows. First, we will generate four random real square matrices of order 10K. We use large matrices because we want the cost of multiplying the matrices to be the dominant factor in the runtime. Then, since the Jupyter notebook has nice features for timing the code, we can spin up a Jupyter notebook<\/a> and perform the timing with the timeit<\/code> command available as part of Jupyter. We will call timeit<\/code> on both functions that will, by default, run the multiplication 7 times and calculate the mean and standard deviation of the collected run-times. This is all done in the following Jupyter Notebook snippet.<\/p>\n\n\n\n
import numpy as np\nfrom matrix_mult import hyperbolic_matrix_mult, complex_matrix_mult\n\nn = 10000\nA = np.random.rand(n, n)\nB = np.random.rand(n, n)\nC = np.random.rand(n, n)\nD = np.random.rand(n, n)\n\n%timeit hyperbolic_matrix_mult(A, B, C, D)\n%timeit complex_matrix_mult(A, B, C, D)<\/pre>\n\n\n\n
After running this for about 45 minutes on my machine, here are the results. The first line shows the runtime of the method using split-complex numbers and the second one is the runtime of the naive complex matrix implementation.<\/p>\n\n\n\n
49.9 s \u00b1 388 ms per loop (mean \u00b1 std. dev. of 7 runs, 1 loop each)\n1 min 2s \u00b1 985 ms per loop (mean \u00b1 std. dev. of 7 runs, 1 loop each)<\/pre>\n\n\n\n
Already from this simple test we see that the improvement in time of the new algorithm over naive complex multiplication is about 20% which is not bad. Stay tuned for more thourough testing in the next post.<\/p>\n
0<\/span><\/a><\/div> <\/div> 
<\/div><\/div>
<\/div>","protected":false},"excerpt":{"rendered":"
In my previous post, I showed that split-complex numbers can be used to speed up complex matrix multiplication. In this post I will do a quick measurement on exactly how much faster is the new approach when compared to the naive implementation in practice. Since we are using 3 real matrix multiplications in the new […]<\/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":[16,14,13],"class_list":["post-1078","post","type-post","status-publish","format-standard","hentry","category-hyperbolic-numbers","tag-fast-matrix-multiplication","tag-hyperbolic-numbers","tag-split-complex-numbers"],"_links":{"self":[{"href":"https:\/\/konrad.burnik.org\/wordpress\/wp-json\/wp\/v2\/posts\/1078","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=1078"}],"version-history":[{"count":30,"href":"https:\/\/konrad.burnik.org\/wordpress\/wp-json\/wp\/v2\/posts\/1078\/revisions"}],"predecessor-version":[{"id":1121,"href":"https:\/\/konrad.burnik.org\/wordpress\/wp-json\/wp\/v2\/posts\/1078\/revisions\/1121"}],"wp:attachment":[{"href":"https:\/\/konrad.burnik.org\/wordpress\/wp-json\/wp\/v2\/media?parent=1078"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/konrad.burnik.org\/wordpress\/wp-json\/wp\/v2\/categories?post=1078"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/konrad.burnik.org\/wordpress\/wp-json\/wp\/v2\/tags?post=1078"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}