Take the 2-minute tour ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.

I have a project where I need to use quadratic fields Specifically numbers of the form $a + b \sqrt{-3}$ with $a,b \in \mathbb{Q}$.

For example here are the prime numbers in Eisenstein integers:

I do not want to use sage. I would like to write my own data type to incorporate numpy. PARI would be useful - but it's not compatible with Python.

  • Addition for these objects is pretty clear $$(a_1 + b_1 \sqrt{-3}) + (a_2 + b_2 \sqrt{-3}) = (a_1 + a_2) + (b_1+b_2) \sqrt{-3}$$
  • Multiplication is a little more delicate but we can hard code it as well $$(a_1 + b_1 \sqrt{-3}) \times (a_2 + b_2 \sqrt{-3}) = (a_1 a_2 - 3 b_1 b_2) + (a_1 b_2 + a_2 b_1)\sqrt{-3}$$
  • My datatype also needs to accommodate division. For simplicity let's take the reciprocal: $$ \frac{1}{a + b \sqrt{-3}} = \frac{a - b \sqrt{-3}}{a^2 + 3b^2}$$

Is there a natural matrix-based way to encode these operations, similar to how $\mathbb{C}$ can be written in terms of $2 \times 2 $ matrices?

$$ \left( \begin{array}{cc} a & b \\ -b & a \end{array}\right)$$

Maybe I will just hard-code the operations as triples with the three operations outlined above. Any ideas?

share|improve this question
add comment

2 Answers 2

For $a+b\sqrt{-3}$ you can use the representation $$\begin{pmatrix}a&-3b\\b&a\end{pmatrix}$$ Addition works obviously. For multiplication, you can verify $$\begin{pmatrix}a_1&-3b_1\\b_1&a_1\end{pmatrix}\begin{pmatrix}a_2&-3b_2\\b_2&a_2\end{pmatrix} = \begin{pmatrix}a_1a_2-3b_1b_2&-3(a_1b_2+b_1a_2)\\a_1b_2+b_1a_2&a_1a_2-3b_1b_2\end{pmatrix}$$ which preserves the representation, thus we have a ring homomorphism.

Taking the determinant of the matrix gives the (squared) norm $a^2+3b^2$, thus reciprocals correspond to inverse matrices, as expected.

You have already considered using triples, by which I assume you'd use integers and a common denominator. That approach may be useful in the matrix representation as well.

Update: A general method for matrix representations uses the companion matrix. For example, suppose you want to represent $a+b\omega$ instead where $\omega=\exp(\frac{2\pi\mathrm{i}}{3})$, thus $\omega^2+\omega+1=0$. The companion matrix of $\omega$ is $\begin{pmatrix}0&-1\\1&-1\end{pmatrix}$, and this behaves in all its associated ring operations like $\omega$ itself. Of course, $1$ can be represented as $\begin{pmatrix}1&0\\0&1\end{pmatrix}$; therefore a matrix representation of $a+b\omega$ is $$\begin{pmatrix}a&-b\\b&a-b\end{pmatrix}$$ You may want to verify that this is a ring homomorphism. For addition, this is easy to see. For multiplication, the corresponding formulae are now $$\begin{align} (a_1+b_1\omega)(a_2+b_2\omega)&=(a_1a_2-b_1b_2)+(a_1b_2+b_1a_2-b_1b_2)\omega \\\begin{pmatrix}a_1&-b_1\\b_1&a_1-b_1\end{pmatrix} \begin{pmatrix}a_2&-b_2\\b_2&a_2-b_2\end{pmatrix} &= \begin{pmatrix}a_1a_2-b_1b_2&-(a_1b_2+b_1a_2-b_1b_2)\\ a_1b_2+b_1a_2-b_1b_2&a_1a_2-a_1b_2-b_1a_2\end{pmatrix} \end{align}$$

share|improve this answer
add comment

I'm guessing you want exact rational arithmetic for everything, as floating point errors could make $1/z$ not in $\mathbb{Q}[\sqrt{-3}]$ even if $z$ is. For that, you might want to have a look at the SymPy package; if you don't use their rational data type directly, it could serve as inspiration for your own hand-rolled version. You could then build your quadratic field type on top of whatever rational number type you choose.

No matter how you represent the elements of your field, you can overload operators in Python using "magic methods". See also this SO post on creating your own numeric type in Python.

I don't think there would be that much more work coding a representation of an element of a quadratic field either as a 2 x 2 matrix of rational numbers or as a pair of rational numbers, since the arithmetic operations aren't that complicated. However, I suspect the second approach will be faster.

share|improve this answer
1  
It may be interesting to compare the practical performance of numpy-accelerated matrix ops with those of user-defined data types. Not sure about what the winner would be. –  ccorn Apr 23 at 17:10
    
Yes that's true, numpy does have a lot of Cython + hand-coded optimizations on the C side to make things faster. You'd have to redo some of that yourself to achieve the same effect. Nonetheless, functionality should come first and later one can worry about speed. –  Daniel Shapero Apr 23 at 18:04
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.