Talk:QR decomposition: Difference between revisions

From Rosetta Code
Content added Content deleted
No edit summary
Line 12: Line 12:
I believe the code has a problem. Under certain circumstances, division by zero will occur in the line
I believe the code has a problem. Under certain circumstances, division by zero will occur in the line
vdiv(e, vnorm(e, m->m), e, m->m);
vdiv(e, vnorm(e, m->m), e, m->m);
The reason seems to be that the loop which creates the Householder matrices loops over the number of rows in the input matrix m (m->m), and attempts to extract a column with the same index as the row index from the matrix z (which has the same dimensions as m). This is fine if m->m <= m->n. For purposes of solving over-determined equation systems, however, we will have m->m > m->n. Consequently, we will try to extract non-existing columns from the matrix z, and what they contain will be indeterminate. Should it happen that all column elements are zero, the division by zero referred to above will take place. This of course renders the whole calculation useless.
The reason seems to be that the loop which creates the Householder matrices loops over the number of rows in the input matrix m (m->m), and attempts to extract a column with the same index as the row index from the matrix z (which has the same dimensions as m). This is fine if m->m <= m->n. For purposes of solving over-determined equation systems, however, we will have m->m > m->n. Consequently, we will try to extract non-existing columns from the matrix z, and what they contain will be indeterminate. Should it happen that all column elements are zero, the division by zero referred to above will take place. This of course renders the whole calculation useless. --[[User:Ernstegon|Ernstegon]] 21:22, 17 November 2012 (UTC)


== Common Lisp example ==
== Common Lisp example ==

Revision as of 21:22, 17 November 2012

usage?

What does "and the usage for linear least squares problems on the example from Polynomial_regression" mean, specifically, as a task requirement? --Rdm 16:02, 17 June 2011 (UTC)

It means that there already is a existing task on RC (Polynomial regression) which requires linear least squares, and since LLS is one use case for QR, that task can be used here as an example. The Go and R solutions of the Polynomial regression already used QR instead of the normal equations approach. --Avi 20:52, 17 June 2011 (UTC)
According to the wikipedia page on least squares, QR reduction is supposed to be more numerically stable than faster approaches. But we can solve the Polynomial regression example exactly, so I am not sure that that example is a good one for QR reduction least squares fitting. --Rdm 16:34, 17 June 2011 (UTC)
The advantage is that it is already existing, has many solutions and can be used as a comparison. --Avi 20:52, 17 June 2011 (UTC)

C example

The code does do the job, but is quite ugly, and overly long. Much improvement is needed, and all the matrix_delete() calls would make you appreciate garbage collection that much more. --Ledrug 01:26, 29 June 2011

Is the D version (that is a port of the Common Lisp version) any better?

I believe the code has a problem. Under certain circumstances, division by zero will occur in the line

  vdiv(e, vnorm(e, m->m), e, m->m);

The reason seems to be that the loop which creates the Householder matrices loops over the number of rows in the input matrix m (m->m), and attempts to extract a column with the same index as the row index from the matrix z (which has the same dimensions as m). This is fine if m->m <= m->n. For purposes of solving over-determined equation systems, however, we will have m->m > m->n. Consequently, we will try to extract non-existing columns from the matrix z, and what they contain will be indeterminate. Should it happen that all column elements are zero, the division by zero referred to above will take place. This of course renders the whole calculation useless. --Ernstegon 21:22, 17 November 2012 (UTC)

Common Lisp example

What is eye in make-householder? In array-range m and n seem useless.

Thanks for pointing this out. (eye n) returns a nxn identity matrix. I overlooked that. (identity) is an already taken Common Lisp function, so I couldnt use that. The terminology is following matlab/octave's naming. Your second point is also correct, and these two local bindings can be removed. Thanks. --Avi 16:21, 12 July 2011 (UTC)

Description flow

In response to [1], I find the task description difficult to follow, as its narrative form interleaves mathematical formulae and expressions with English text. I tried splitting it up as I did in Gauss-Legendre_Quadrature, but I was unable to. If someone could organize the task description to visually separate the formulas from the written text, that'd be great. --Michael Mol 15:34, 4 July 2011 (UTC)

The narative interleaves formulas and text since this is how most papers are written. The formulas are not meant to be a pseudocode in mathematical notation which can then be reimplemented line by line, I have given a non-optimized Common Lisp version which follows the steps and should be easy to follow and can be used as a reference. --Avi 16:25, 12 July 2011 (UTC)

Pseudocode request

As it stands, I think this task description has nothing near good enough to inform a programmer how to solve it.It relies too much on correct interpretation of the mathematical equations. O.K. this talk page then goes on to state that the Lisp example should be followed, but the lisp example is poorly commented.

How about better comments on what each Lisp function needs, does, and returns. In programming terms. Then add it to the task description as the pseudocode to follow? --Paddy3118 14:08, 23 July 2011 (UTC)

Draft status

Also in response to [2], the simplest way to get a task from draft to non-draft status is to leave a note here asking if there are any further issues that people would like resolved. So I'll ask it; are there any issues or points of confusion in this task that people would like to see resolved? --Michael Mol 15:34, 4 July 2011 (UTC)

Please fix the CommonLisp version.
I did now. Thanks for your hints. Are there any other objections? --Avi 17:02, 12 July 2011 (UTC)
What is this line of make-householder doing? (beta (/ 2 (mmul (mtp v) v))))
It creates a local variable (which is often used in articles about the QR decomposition) with the value , and is used to create the Householder matrix . I also could have written the first formula directly instead of that. --Avi 18:18, 13 July 2011 (UTC)
<lang lisp>(m- (eye m)
   (.* (/ 2 (mmul (mtp v) v)))
       (mmul v (mtp v))))</lang>
is a scalar value (since is a doct product), not a matrix, so making it a array will cause a type error. --Avi 16:07, 14 July 2011 (UTC)
What you have reverted breaks the code to me. Maybe I am using a different Common Lisp compiler? http://ideone.com/UUsVG
I have to agree with you once again. In my development version, I used a slightly different matrix multiplication routine (mmul), that turns a 1x1 array, like in the case of , to a scalar. The mmul on RC does not do that, so your fix was correct, and I will revert my change. Thanks for your effort. --Avi 09:35, 16 July 2011 (UTC)
Are there any reasons to keep this draft? The task appears to be clear enough (mathematical, but that's just its nature) and there are multiple correct implementations. –Donal Fellows 13:07, 23 September 2011 (UTC)
My only complaint is that it's very difficult to grok, with the way the task description is laid out. But that's something someone can come along and clean up. I agree; there's no substantive reason to keep this as a draft. --Michael Mol 13:37, 23 September 2011 (UTC)