Author Archives: Konrad

CCA 2024 Conference

Leave a reply

This week, during my vacation, I attended the Twenty-First International Conference on Computability and Complexity in Analysis. It was held at Swansea in Wales, UK. There I presented joint work with Zvonko Iljazović and Lucija Validžić. The title of the presentation was Computability of One-point Metric Bases. The slides can be found here.

Some photos from Swansea, including the Bay Campus can be found below.

Slides

CCA_2024_Burnik_Iljazovic_Validzic

0

Split-Complex Numbers as a Clifford Algebra

Leave a reply


The split-complex numbers are a special case of Clifford Algebra. This can be seen as follows. Let X = \mathbb{R}^1. Let e_1 = \langle a \rangle with a \not = 0 be a basis element of \mathbb{R}^1. Then the Clifford Algebra \mathcal{C}(\mathbb{R}^1) is defined as follows. The elements of the Clifford algebra are \alpha + \beta e_1. Setting the rule for the Clifford product e_1 \vee e_1 as

(1)   \begin{equation*}e_1 \vee e_1 = 1\end{equation*}


yields

    \[(\alpha_1 + \beta_1 e_1) \vee (\alpha_2 + \beta_2 e_1) = (\alpha_1 \alpha_2 + \beta_1 \beta_2) + (\alpha_1 \beta_2 + \beta_1 \alpha_2) e_1\]


The isomorphism is 1 \mapsto 1, e_1 \mapsto j. On the other hand, setting the rule to e_1 \vee e_1 = 0 or e_1 \vee e_1 = -1 in (1) yields a correspondence with dual-numbers or complex numbers respectively. I am planning to expand on this fact in one of the subsequent posts.

0

Implementation of Faster Complex Matrix Multiplication via Split-Complex Numbers

Leave a reply

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 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. In the following listing the hyperbolic_matrix_mult function is the new approach that uses split-complex numbers and complex_matrix_mult is the function implementing the naive complex matrix multiplication.

# matrix_mult.py

import numpy as np

def hyperbolic_matrix_mult(Z1, Z2, W1, W2):
    X = 0.5 * (Z1 + Z2).dot(W1 + W2)
    Y = 0.5 * (Z1 - Z2).dot(W1 - W2)
    return X + Y - 2.0 * Z2.dot(W2), X - Y

def complex_matrix_mult(Z1, Z2, W1, W2):
    return Z1.dot(W1) - Z2.dot(W2), Z1.dot(W2) + Z2.dot(W1)

I will be running the test on my MacBook laptop with the following specs:

Hardware Overview:

  Model Name:                   MacBook Pro
  Model Identifier:             MacBookPro13,3
  Processor Name:               Quad-Core Intel Core i7
  Processor Speed:              2,6 GHz
  Number of Processors:         1
  Total Number of Cores:        4
  L2 Cache (per Core):          256 KB
  L3 Cache:                     6 MB
  Hyper-Threading Technology:   Enabled
  Memory:                       16 GB

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 and perform the timing with the timeit command available as part of Jupyter. We will call timeit 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.

import numpy as np
from matrix_mult import hyperbolic_matrix_mult, complex_matrix_mult

n = 10000
A = np.random.rand(n, n)
B = np.random.rand(n, n)
C = np.random.rand(n, n)
D = np.random.rand(n, n)

%timeit hyperbolic_matrix_mult(A, B, C, D)
%timeit complex_matrix_mult(A, B, C, D)

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.

49.9 s ± 388 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
1 min 2s ± 985 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

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.

0

Faster Complex Matrix Multiplication via Split-Complex Numbers

Leave a reply

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

    \[ Z_1 Z_2 = (A + i B) (C + iD) = (A C - B D) + i(AD + BC) \]

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 W_1 = A + j B and W_2 = C + j D and rewriting them in basis \{\iota, \iota^*\} as follows

    \begin{align*}W_1 & = (A+B) \iota + (A-B) \iota^* \\W_2 &= (C+D) \iota + (C-D) \iota^*\end{align*}

we have

    \[ W_1 W_2 = (A+B)(C+D) \iota + (A-B)(C-D) \iota^* \]

which requires only 2 real matrix multiplications. This all follows from my previous post.

Let us now define

    \begin{align*}X & := \frac{1}{2} (A + B) (C + D) \\ Y & := \frac{1}{2} (A - B) (C - D).\end{align*}

We have

    \[ W_1 W_2 = (X + Y ) + j (X - Y). \]

But now, since

    \[ W_1 W_2 = (AC + BD) + j (AD + BC) \]

then by comparison AC + BD = X + Y and AD + BC = X - Y.

Finally, from this and the fact AC - BD = X + Y - 2 BD we have

    \[Z_1 Z_2 = (X + Y - 2 BD) + i(X - Y)\]

which requires only 3 real matrix multiplications, namely (A+B)(C+D), (A-B)(C-D) and BD.

EDIT: A simple implementation of this approach can be found here.

0

This blog now runs on a new server

The blog has migrated to a new server yesterday! It was running on an old server with outdated software since 2013. Special thanks to my brother Kristijan for jumping in with his expertise to do a quick setup and migration of the blog to the new and improved server!

Enjoy the speed and stability of the new blog!

0

Split-complex numbers revisited

A split-complex number is an algebraic expression of the form x + j y where x, y \in \mathbb{R} and j^2 = + 1 where j \not = \pm 1. We can write a split-complex number simply as a pair of real numbers (x,y). Adding two split-complex numbers when represented as pairs is done component-wise. Hence, given (a, b) and (c, d) addition is defined as

    \[(a,b) + (c,d) = (a+c, b+d).\]

However, the product of two split-complex numbers is not defined component-wise since

    \[(a,b) \cdot (c,d) = (ac + bd, ad + bc).\]

One nice property of split-complex numbers is that we can change their representation in order to make multiplication component-wise as well.

Let

    \begin{align*}\iota = \frac{1 + j}{2} \ \mbox{ and } \ \iota^{*} = \frac{1 - j}{2}.\end{align*}

Now each hyperbolic number z = a + j b can uniquely be written in terms of
{\iota, \iota^* } as follows.

    \[z = (a + b) \iota + (a - b) \iota^{*}\]

From here, the multiplication of two numbers \tilde{z_1} = a \iota + b \iota^{*} and \tilde{z_2} = c \iota + d\iota^{*} is now given component-wise by

    \[ \tilde{z_1} \tilde{z_2} = a c \iota + b d \iota^{*}\]

In this sense the transformed split-complex numbers algebraically behave just like two copies of real numbers since the algebraic operations are performed in each copy independently. More on this alternative representation of split-complex numbers in subsequent posts.

0