Sage: Ticket #18365: Definition of LU decomposition of a matrix depends on the base ring
https://trac.sagemath.org/ticket/18365
<p>
As reported on <a class="ext-link" href="http://ask.sagemath.org/question/26713/lu-descomposition-for-a-matrix/"><span class="icon"></span>this ask question</a>, there is an inconsistency in the definition of the LU decomposition of a matrix depending on its base ring. If a matrix <code>A</code> belongs to <code>ZZ</code>, <code>QQ</code>, <code>AA</code>, <code>QQbar</code>, <code>A.LU()</code> returns a triple <code>(P,L,U)</code> such that <code>A=PLU</code>. If a matrix <code>A</code> belongs to <code>RDF</code>, <code>A.LU()</code> returns a triple <code>(P,L,U)</code> such that <code>PA=LU</code>. For example:
</p>
<pre class="wiki">sage: A = random_matrix(ZZ,4)
sage: A.LU()
(
[0 1 0 0] [ 1 0 0 0] [ 72 -4 -38 0]
[0 0 1 0] [ 0 1 0 0] [ 0 -1 -2 10]
[1 0 0 0] [ 1/36 8/9 1 0] [ 0 0 17/6 -80/9]
[0 0 0 1], [-1/36 1/9 -1 1], [ 0 0 0 -17]
)
sage: B = A.change_ring(RDF)
sage: B.LU()
(
[0.0 0.0 1.0 0.0]
[1.0 0.0 0.0 0.0]
[0.0 1.0 0.0 0.0]
[0.0 0.0 0.0 1.0],
[ 1.0 0.0 0.0 0.0]
[ 0.0 1.0 0.0 0.0]
[ 0.0277777777778 0.888888888889 1.0 0.0]
[-0.0277777777778 0.111111111111 -1.0 1.0],
[ 72.0 -4.0 -38.0 0.0]
[ 0.0 -1.0 -2.0 10.0]
[ 0.0 0.0 2.83333333333 -8.88888888889]
[ 0.0 0.0 0.0 -17.0]
)
sage: B.LU()[0] == A.LU()[0]
False
sage: B.LU()[0] == A.LU()[0].transpose()
True
sage:
</pre><p>
The aim of this ticket is to fix this inconsistency and choose a common definition for all rings.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/18365
Trac 1.1.6tmonteilMon, 04 May 2015 15:17:11 GMT
https://trac.sagemath.org/ticket/18365#comment:1
https://trac.sagemath.org/ticket/18365#comment:1
<p>
It is worth noticing that the source code for matrices over <code>RDF</code> calls <code>scipy.linalg.lu</code> which returns a triple <code>(P,L,U)</code> such that <code>A=PLU</code> and then transpose <code>P</code> with the documentation:
</p>
<pre class="wiki"># Numpy has a different convention than we had with GSL
# So we invert (transpose) the P to match our prior behavior
# TODO: It's an awful waste to store a huge matrix for P, which
# is just a simple permutation, really.
</pre><p>
So, i guess this extra transposition should be reverted, so that it becomes consistent with both <code>scipy</code> and the implementation for exact rings.
</p>
TicketkcrismanMon, 04 Mar 2019 20:19:00 GMTcc set
https://trac.sagemath.org/ticket/18365#comment:2
https://trac.sagemath.org/ticket/18365#comment:2
<ul>
<li><strong>cc</strong>
<em>kcrisman</em> added
</li>
</ul>
TicketkcrismanMon, 04 Mar 2019 20:20:04 GMT
https://trac.sagemath.org/ticket/18365#comment:3
https://trac.sagemath.org/ticket/18365#comment:3
<p>
Probably in principle the old behavior should be deprecated ... but the inconsistency is annoying, agreed.
</p>
Ticketgh-ChamanAgrawalFri, 08 Mar 2019 11:53:48 GMTstatus, cc changed; commit, branch, author set
https://trac.sagemath.org/ticket/18365#comment:4
https://trac.sagemath.org/ticket/18365#comment:4
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>cc</strong>
<em>gh-ChamanAgrawal</em> added
</li>
<li><strong>commit</strong>
set to <em>251254086d59c476e0b3db3b90c94c357063a357</em>
</li>
<li><strong>branch</strong>
set to <em>u/gh-ChamanAgrawal/18365_RDF_LU</em>
</li>
<li><strong>author</strong>
set to <em>Chaman Agrawal</em>
</li>
</ul>
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=251254086d59c476e0b3db3b90c94c357063a357"><span class="icon"></span>2512540</a></td><td><code>Reverted transpose to maintain consistency with scipy, numpy</code>
</td></tr></table>
Ticketgh-ChamanAgrawalFri, 08 Mar 2019 12:05:50 GMT
https://trac.sagemath.org/ticket/18365#comment:5
https://trac.sagemath.org/ticket/18365#comment:5
<p>
I have removed to the extra copy of the matrix and also reverted the transposing step to maintain consistent behavior with scipy and also with <code>LU()</code> in matrices of other class in sagemath.
</p>
TicketSimonKingMon, 01 Apr 2019 07:25:40 GMT
https://trac.sagemath.org/ticket/18365#comment:6
https://trac.sagemath.org/ticket/18365#comment:6
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/18365#comment:3" title="Comment 3">kcrisman</a>:
</p>
<blockquote class="citation">
<p>
Probably in principle the old behavior should be deprecated ... but the inconsistency is annoying, agreed.
</p>
</blockquote>
<p>
The proposed change does not change the syntax of using the <code>.LU()</code> method, but changes the semantic of the output. How would it be possible to deprecate it?
</p>
<p>
Do you say that if the <code>.LU()</code> method is used for a matrix over RDF then a deprecation warning should be used? That warning would appear also in the case that the user expects the new (not the old) behaviour, i.e., when a warning is inappropriate.
</p>
TicketkcrismanMon, 01 Apr 2019 11:51:23 GMT
https://trac.sagemath.org/ticket/18365#comment:7
https://trac.sagemath.org/ticket/18365#comment:7
<blockquote class="citation">
<p>
The proposed change does not change the syntax of using the <code>.LU()</code> method, but changes the semantic of the output. How would it be possible to deprecate it?
</p>
</blockquote>
<p>
Good point. Perhaps we need to just put a visible note in the documentation that might help clarify if someone is perplexed by the output changing - I guess that was my point, that it is a "silent" change. But they should agree over all rings, yes.
</p>
Ticketgh-ChamanAgrawalMon, 01 Apr 2019 12:04:51 GMT
https://trac.sagemath.org/ticket/18365#comment:8
https://trac.sagemath.org/ticket/18365#comment:8
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/18365#comment:7" title="Comment 7">kcrisman</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
The proposed change does not change the syntax of using the <code>.LU()</code> method, but changes the semantic of the output. How would it be possible to deprecate it?
</p>
</blockquote>
<p>
Good point. Perhaps we need to just put a visible note in the documentation that might help clarify if someone is perplexed by the output changing - I guess that was my point, that it is a "silent" change. But they should agree over all rings, yes.
</p>
</blockquote>
<p>
I think along with a note in the documentation <code>LU()</code> should also give a warning on using for this behavior change, what do you think?
</p>
TicketSimonKingMon, 01 Apr 2019 12:09:59 GMT
https://trac.sagemath.org/ticket/18365#comment:9
https://trac.sagemath.org/ticket/18365#comment:9
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/18365#comment:8" title="Comment 8">gh-ChamanAgrawal</a>:
</p>
<blockquote class="citation">
<p>
I think along with a note in the documentation <code>LU()</code> should also give a warning on using for this behavior change, what do you think?
</p>
</blockquote>
<p>
I don't think so. A warning (in the sense of: "If M.LU() is called then a warning is printed") is disturbing, because the mere fact of calling <code>.LU()</code> is <em>not</em> a problem. What is a potential problem is whether or not the user expects the output in a particular form. And we cannot guess on the expectation of the user. Hence, certainly it should be written in the documentation that there has been a change, give an example for which that change happens, and insert a link to this ticket. The syntax for such link in the docstrings is
</p>
<pre class="wiki">See :trac:`18365`.
</pre><p>
But there should be no warning inserted into the code.
</p>
TicketgitMon, 01 Apr 2019 13:54:22 GMTcommit changed
https://trac.sagemath.org/ticket/18365#comment:10
https://trac.sagemath.org/ticket/18365#comment:10
<ul>
<li><strong>commit</strong>
changed from <em>251254086d59c476e0b3db3b90c94c357063a357</em> to <em>6fdae81bf4fd40caff8e877a1b4caa8c58db4e66</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=6fdae81bf4fd40caff8e877a1b4caa8c58db4e66"><span class="icon"></span>6fdae81</a></td><td><code>Added Note for behaviour change</code>
</td></tr></table>
Ticketgh-ChamanAgrawalMon, 01 Apr 2019 13:57:24 GMT
https://trac.sagemath.org/ticket/18365#comment:11
https://trac.sagemath.org/ticket/18365#comment:11
<p>
I have added a note for the change as below, any suggestion for change?
</p>
<pre class="wiki">.. NOTE::
The behaviour of ``LU()`` has been changed. Earlier ``LU()``
returned ``P,L,U`` such that ``P*A=L*U``, where ``P`` represents
the permutation and is the matrix inverse of the ``P`` returned
by this method. The computation of this matrix inverse can be accomplished
quickly with just a transpose as the matrix is orthogonal/unitary.
For Details See :trac:`18365`.
EXAMPLES::
sage: m = matrix(RDF,4,range(16))
sage: P,L,U = m.LU()
sage: P*L*U # rel tol 2e-16
[ 0.0 1.0 2.0 3.0]
[ 4.0 5.0 6.0 7.0]
[ 8.0 9.0 10.0 11.0]
[12.0 13.0 14.0 15.0]
Below example illustrate the change in behaviour of ``LU()``. ::
sage: m == P*L*U
True
sage: P*m == L*U
False
</pre>
TicketchapotonSat, 04 Jan 2020 08:33:53 GMTmilestone, summary changed
https://trac.sagemath.org/ticket/18365#comment:12
https://trac.sagemath.org/ticket/18365#comment:12
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.7</em> to <em>sage-9.1</em>
</li>
<li><strong>summary</strong>
changed from <em>Definition of LU descomposition of a matrix depends on the base ring</em> to <em>Definition of LU decomposition of a matrix depends on the base ring</em>
</li>
</ul>
Ticketgh-mwageringelThu, 27 Feb 2020 22:46:04 GMT
https://trac.sagemath.org/ticket/18365#comment:13
https://trac.sagemath.org/ticket/18365#comment:13
<p>
I suggest that this gets merged now, despite the backwards incompatibility.
</p>
Ticketgh-mwageringelSun, 08 Mar 2020 13:24:29 GMTcommit, branch changed
https://trac.sagemath.org/ticket/18365#comment:14
https://trac.sagemath.org/ticket/18365#comment:14
<ul>
<li><strong>commit</strong>
changed from <em>6fdae81bf4fd40caff8e877a1b4caa8c58db4e66</em> to <em>96a9f92abda84d6dd863c8604f23081425043110</em>
</li>
<li><strong>branch</strong>
changed from <em>u/gh-ChamanAgrawal/18365_RDF_LU</em> to <em>u/gh-mwageringel/18365</em>
</li>
</ul>
<p>
I have made small formatting changes to the documentation and removed trailing whitespace. I will let the patchbot run on this ticket once more and then set it to positive.
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=96a9f92abda84d6dd863c8604f23081425043110"><span class="icon"></span>96a9f92</a></td><td><code>18365: reviewer changes</code>
</td></tr></table>
Ticketgh-mwageringelSun, 08 Mar 2020 13:28:07 GMTreviewer set
https://trac.sagemath.org/ticket/18365#comment:15
https://trac.sagemath.org/ticket/18365#comment:15
<ul>
<li><strong>reviewer</strong>
set to <em>Markus Wageringel</em>
</li>
</ul>
Ticketgh-mwageringelWed, 11 Mar 2020 18:48:30 GMTstatus changed
https://trac.sagemath.org/ticket/18365#comment:16
https://trac.sagemath.org/ticket/18365#comment:16
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
TicketvbraunThu, 12 Mar 2020 22:48:18 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/18365#comment:17
https://trac.sagemath.org/ticket/18365#comment:17
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>branch</strong>
changed from <em>u/gh-mwageringel/18365</em> to <em>96a9f92abda84d6dd863c8604f23081425043110</em>
</li>
</ul>
Ticket