eigenvalues and eigenvectors using arb

[mezzarobba]

The wrappers are marked as experimental because the corresponding arb functions are.

Component: linear algebra

Author: Marc Mezzarobba

Branch: b792cbd

Reviewer: Sébastien Labbé

Issue created by migration from https://trac.sagemath.org/ticket/30393

[mezzarobba]

Branch: u/mmezzarobba/acb_eig

[mezzarobba]

Commit: 1d42e2b

[mezzarobba]

New commits:

1d42e2b

#30393 wrap arb's experimental eigensolver

[seblabbe]

comment:2

Note that the signature of that method is changing in #29243. Maybe better to follow that?

[sagetrac-git]

Changed commit from 1d42e2b to e89ac63

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

e89ac63

#30393 match the new interface introduced in #29243

[mezzarobba]

comment:4

Replying to @seblabbe:

Note that the signature of that method is changing in #29243. Maybe better to follow that?

Thank you. I'm not setting that ticket as a dependency though, since these methods are experimental anyway.

[sagetrac-git]

Changed commit from e89ac63 to 56f22b1

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

56f22b1

#30393 match the new interface introduced in #29243

[seblabbe]

comment:6

Few comments:

• "unable to certify the eigenvalues of this interval matrix", I would avoid the usage of the word interval which reminds of the CIF since the matrix belongs rather to the CBF.
• the other input should be documented as related to the generalized eigenvalue problem in the input block and/or in the raise NotImplementedError.

What should happen when the parent is RealBallField?

sage: M = matrix(3, [1, 1, 1, 1, 0, 0, 0, 1, 0])                                                       
sage: MRBF = M.change_ring(RBF)                                                                        
sage: MRBF.eigenvalues() 
KeyError: '_PolynomialRing_singular_repr__singular'
...
During handling of the above exception, another exception occurred:
...
AttributeError: 'PolynomialRing_field_with_category' object has no attribute '_PolynomialRing_singular_repr__singular'
...
During handling of the above exception, another exception occurred:
...
TypeError: no conversion of this ring to a Singular ring defined
...
During handling of the above exception, another exception occurred:
...
NotImplementedError: 

Can this benefits from your current branch?

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

7f1b45e

#30393 match the new interface introduced in #29243

[sagetrac-git]

Changed commit from 56f22b1 to 7f1b45e

[mezzarobba]

comment:8

Replying to @seblabbe:

Few comments:

• "unable to certify the eigenvalues of this interval matrix", I would avoid the usage of the word interval which reminds of the CIF since the matrix belongs rather to the CBF.
• the other input should be documented as related to the generalized eigenvalue problem in the input block and/or in the raise NotImplementedError.

Done. (Though the second point is bugware. What we need IMHO is for each method's documentation to include or link to that of the methods it overrides, and to change the way we write docstrings to take advantage of that. It doesn't make any sense to repeat the same information over and over with no automatic way of keeping the various places in sync.)

What should happen when the parent is RealBallField?

[...]

Can this benefits from your current branch?

In principle yes (and matrices over RR and CC can benefit too), but at the moment we don't even have a dedicated class for matrices over RBF. I think we should keep that for another ticket, and probably wait until the methods are no longer marked experimental.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

5f6fb40

#30393 wrap arb's experimental eigensolver

[sagetrac-git]

Changed commit from 7f1b45e to 5f6fb40

[seblabbe]

comment:10

Replying to @mezzarobba:

Replying to @seblabbe:
Done.

Thanks.

(Though the second point is bugware. What we need IMHO is for each method's documentation to include or link to that of the methods it overrides, and to change the way we write docstrings to take advantage of that. It doesn't make any sense to repeat the same information over and over with no automatic way of keeping the various places in sync.)

I agree with your point (out of sync). But, I do hate the documentation of G.plot(**kwds) which does not say which options are available.

That being said, I think my point in comment 2 was mostly to avoid using the extend option as a positional argument like:

sage: M = M.change_ring(CBF)
sage: M.eigenvalues(True)

since it will not be the 1st argument anymore after #29243. If you can force the extend to be a keyword argument like def eigenvalues(self, *, extend=False), then for me it is okay, even without the other argument. Do you mind to remove the other argument? Sorry for my slow convergence on clarifying my point of view.

I think we should keep that for another ticket, and probably wait until the methods are no longer marked experimental.

I agree.

[seblabbe]

comment:11

I get an error while building the documentation:

[dochtml] OSError: docstring of 
sage.matrix.matrix_complex_ball_dense.Matrix_complex_ball_dense.trace:11: 
WARNING: Duplicate explicit target name: "arb documentation".

In fact it seems to be triplicate:

+        See the `Arb documentation <http://arblib.org/acb_mat.html#c.acb_mat_eig_multiple>`_
+        for more information.
...
+        See the `Arb documentation <http://arblib.org/acb_mat.html#c.acb_mat_approx_eig_qr>`_
+        for more information.
...
+        See the `Arb documentation <http://arblib.org/acb_mat.html#c.acb_mat_eig_simple>`_
+        for more information.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

edd1ae0

#30393 work around sphinx issue

[sagetrac-git]

Changed commit from 5f6fb40 to edd1ae0

[mezzarobba]

comment:14

Replying to @seblabbe:

If you can force the extend to be a keyword argument like def eigenvalues(self, *, extend=False), then for me it is okay, even without the other argument. Do you mind to remove the other argument?

It may still be slightly better to have it there, to be compatible with the generic method in case someone explicitly passes a second argument equal to None.

[mezzarobba]

comment:15

Replying to @seblabbe:

I get an error while building the documentation:

[dochtml] OSError: docstring of 
sage.matrix.matrix_complex_ball_dense.Matrix_complex_ball_dense.trace:11: 
WARNING: Duplicate explicit target name: "arb documentation".

I don't understand what is going on (why should two different inline links necessarily have distinct link texts?!), but let's see if the commit I just pushed solves the issue.

[seblabbe]

comment:16

Can you do the following change (x3) ?

-  See the <http://arblib.org/acb_mat.html#c.acb_mat_eig_multiple for
+  See http://arblib.org/acb_mat.html#c.acb_mat_eig_multiple for

[seblabbe]

comment:17

also:

- http://arblib.org/acb_mat.html#c.acb_mat_approx_eig_qr_
+ http://arblib.org/acb_mat.html#c.acb_mat_approx_eig_qr

[seblabbe]

Reviewer: Sébastien Labbé

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

a39c8c6

#30393 work around sphinx issue

[sagetrac-git]

Changed commit from edd1ae0 to a39c8c6

[mezzarobba]

comment:21

Oops. I went too fast indeed, thanks!

---

New commits:

a39c8c6

#30393 work around sphinx issue

[seblabbe]

comment:22

I found the correct fix. In ReStructuredText syntax, one underscore at the end creates a target arb documentation which needs to be unique in the page while two underscores doesn't create such a target. See: https://stackoverflow.com/questions/27420317/restructured-text-rst-http-links-underscore-vs-use

-See the `Arb documentation <http://arblib.org/acb_mat.html#c.acb_mat_eig_multiple>`_
-See the `Arb documentation <http://arblib.org/acb_mat.html#c.acb_mat_approx_eig_qr>`_
-See the `Arb documentation <http://arblib.org/acb_mat.html#c.acb_mat_eig_simple>`_
+See the `Arb documentation <http://arblib.org/acb_mat.html#c.acb_mat_eig_multiple>`__
+See the `Arb documentation <http://arblib.org/acb_mat.html#c.acb_mat_approx_eig_qr>`__
+See the `Arb documentation <http://arblib.org/acb_mat.html#c.acb_mat_eig_simple>`__

Do you want to revert it back to using two underscores?

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

b792cbd

#30393 fix external links in docstrings

[sagetrac-git]

Changed commit from a39c8c6 to b792cbd

[mezzarobba]

comment:24

Replying to @seblabbe:

I found the correct fix.

Oh, I didn't know about the difference, thank you!

Do you want to revert it back to using two underscores?

Done (but untested; I don't want to rebuild the doc right now).

[seblabbe]

comment:25

and I checked that documentation builds ok.

[seblabbe]

comment:26

Replying to @mezzarobba:

Replying to @seblabbe:

I found the correct fix.

Oh, I didn't know about the difference, thank you!

I created #30444 to add it to the documentation.

[vbraun]

Changed branch from u/mmezzarobba/acb_eig to b792cbd

[mwageringel]

Changed commit from b792cbd to none

[mwageringel]

comment:28

While following the examples in the documentation in order to prepare something for the release tours, I noticed that the computed right eigenvectors are wrong. They do not satisfy the eigenvector equation. In fact, it seems to be a problem of transposition. The computed vectors are the rows of the eigenmatrix, but the eigenvectors would be the columns.

sage: from sage.matrix.benchmark import hilbert_matrix
sage: mat = hilbert_matrix(3).change_ring(CBF)
sage: [v[1][0].column() for v in mat.eigenvectors_right()]
⎡ ⎛ [0.827044926972 +/- 1.17e-13] + [+/- 1.08e-13]*I⎞  ⎛[0.459863904366 +/- 5.79e-13] + [+/- 1.22e-13]*I⎞
⎢ ⎜[-0.547448430721 +/- 4.33e-13] + [+/- 1.08e-13]*I⎟  ⎜[0.528290235067 +/- 5.58e-13] + [+/- 1.22e-13]*I⎟
⎣ ⎝[-0.127659329747 +/- 5.74e-13] + [+/- 1.08e-13]*I⎠, ⎝[0.713746885803 +/- 5.34e-13] + [+/- 1.22e-13]*I⎠,

 ⎛ [0.323298435244 +/- 6.18e-13] + [+/- 1.19e-13]*I⎞ ⎤
 ⎜ [0.649006658852 +/- 4.06e-13] + [+/- 1.19e-13]*I⎟ ⎥
 ⎝[-0.688671531671 +/- 4.92e-13] + [+/- 1.19e-13]*I⎠ ⎦

sage: mat.change_ring(CDF).eigenmatrix_right()[1]
⎛  0.8270449269720096  -0.5474484307206746 -0.12765932974653435⎞
⎜ 0.45986390436554375   0.5282902350674367    0.713746885803413⎟
⎝ 0.32329843524449886   0.6490066588517125  -0.6886715316713734⎠

[mezzarobba]

comment:29

Uh, thanks a lot for catching the issue! I thought I has checked...

[mezzarobba]

comment:30

Fixed (I hope) at #30568.

[seblabbe]

comment:31

Oups, I didn't notice that issue during the review. Thanks.

[seblabbe]

comment:32

Another follow up: #33652