Netlib Testing Failures

[srvasanth]

Testing libFLAME library on Netlib's LAPACK test suite (version 3.4.2 & 3.5.0) results in failures in QR decomposition tests.
The failures are observed in only single and double precision QR test cases and not in complex/double complex tests.
Single and double precision variant of QR has libFLAME's C implementation while the complex variants are taking the f2c converted C files.
Attached are the test logs with summary of different tests (libFLAME tested on LAPACK test suites and LAPACK tested on LAPACK test suite). The failure messages in the log files can be reached by searching for SQR or GQR which are the tags for those test cases.
Edit note: BLAS library used for the tests was the library obtained from building Netlib's LAPACK package.

libflame_testing_results_on_lapack3.4.2.txt
libflame_testing_results_on_lapack3.5.0.txt
lapack3.5.0_testing_results_on_lapack3.5.0.txt

[fgvanzee]

@srvasanth I took a look at your netlib test logs, and I think you can safely ignore these as false failures. libflame uses a different Householder transformation than the one in netlib LAPACK. This results in some different (and in our opinion, superior) linear algebra properties in the output of Householder-based operations such as QR factorization. As long as the libflame testsuite passes for QR factorization, then everything should be fine.

(@rvdg may also have a few words about this.)

[srvasanth]

Thank you for the reply Mr. Field.
Currently I am in the process of adding LAPACK-3.9.0 updates into libFLAME. For this, the new and updated functionalities from LAPACK have been converted to C using f2c tool. Here, there are similar failures in single/double precision variants of QR, BD (SVD problems), SG (Symmetric Generalized Eigenvalue problems) test cases when tested using LAPACK-3.9.0 test suite. All these test cases call the Householder transformation functions. Can these failures also be considered as false failures?

[rvdg]

It is important to understand a little bit of the design and structure of libflame. To develop libflame, we used our signature FLAME methodology for deriving algorithms to be correct and the FLAME C API to represent those codes in C. The advantage was that, for a large subset of LAPACK functionality, we ended up with code that has exceptional robustness and is exceptionally “easy" to develop and maintain. The bad news was that, since LAPACK has 2 million or more lines of code, we did not implement all functionality. After all, for the operations that libflame supports we usually have multiple algorithms where LAPACK only has one choice (one blocked and one unblocked). This was simply to great of a task even for someone with Field’s prowess. The good news is that libflame has simply continued to exist without a need for maintenance. An exceptional piece of software engineering that demonstrates the benefits of building on solid theory. A half dozen years ago, Kyungjoo Kim merged the netlib LAPACK code base in with the core libflame code, thus achieving full LAPACK functionality. As you now find out, such functionality does not automatically update itself as LAPACK releases changes. The Householder transformation-based code in libflame is the trickiest part. We use a variant on the WY transform that we call the UT transform [1]. This is the transform that accumulates multiple Householder transformations and then applies them so that matrix-matrix multiplication can be employed. There are two reasons why this is a superior solution: one, it avoid the inversion of a triangular matrix, which makes it more elegant and possibly more numerically stable. The second is that LAPACK views the case where the Householder transformation does not need to introduce zeros (because they are already there or because that part of the current column is already zero) as a special case where instead of using a Householder transformation is uses an identity. While on the surface this makes sense, in practice it causes “fringe” problems that prevent the use of the UT transform and certain (slight) optimizations. The bottom line: LAPACK got a detail wrong. Libflame fixes it. The annoying side-effect of this is that for a square matrix, the very last entry in the result matrix equals the negative of what LAPACK computes. The problem is in then interfacing the LAPACK interface to libflame. Kyungjoo took care of this, but it appears that now great care must be taken to insert new functionality. It may be that the new functionality involves a change in LAPACK’s test suite rather than in its base code. Given that the UT-Austin team is way too busy with BLIS to go back to looking at this, I see a number of possibilities: - It may be that Kyungjoo has time to advise. I am copying this message to him. - You may want to disable the use of all QR factorization related functionality that is provided through libflame and simply have the LAPACK code take care of that. - Modify the test suite so it tests for the result that libflame computes. - Ignore the failures.

…

On Sep 14, 2020, at 7:15 AM, srvasanth ***@***.***> wrote: Thank you for the reply Mr. Field. Currently I am in the process of adding LAPACK-3.9.0 updates into libFLAME. For this, the new and updated functionalities from LAPACK have been converted to C using f2c tool. Here, there are similar failures in single/double precision variants of QR, BD (SVD problems), SG (Symmetric Generalized Eigenvalue problems) test cases when tested using LAPACK-3.9.0 test suite. All these test cases call the Householder transformation functions. Can these failures also be considered as false failures? — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#40 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABLLYJ2KSUT7G3XRNZ3YLM3SFYCPFANCNFSM4Q7Z6JOQ>.

[rvdg]

Hello, When I work on the LAPACK layer of libflame, one of the major problems that I encountered is that the house holder transformation is different between libflame and lapack. For a trivial case, lapack often make a short cut to use trivial unitary matrix when it sees all entires of a column (or row) below a diagonal are zeros. On the other hand, libflame constructs a trivial householder transformation. For some cases, the lapack skips to applying the trivial unitary transformation when it is found. If functions are used as a pair lie dgeqrf (factorize qr) and dormqr (apply qr), it uses the same transformations and it would work. If the LAPACK somehow mixes internal functions (e.g., compute qr factorization and it uses internal apply-functions of house holders) to create a new functionality, libflame lapack version may not pass such a test. If I remembered correct, I used the lapack test suite of 3.5.0 when I worked on the code. It may not pass with 3.9.0 and it may need another overhaul. Best Kyungjoo On Sep 14, 2020, at 7:05 AM, Robert van de Geijn <rvdg@cs.utexas.edu<mailto:rvdg@cs.utexas.edu>> wrote: It is important to understand a little bit of the design and structure of libflame. To develop libflame, we used our signature FLAME methodology for deriving algorithms to be correct and the FLAME C API to represent those codes in C. The advantage was that, for a large subset of LAPACK functionality, we ended up with code that has exceptional robustness and is exceptionally “easy" to develop and maintain. The bad news was that, since LAPACK has 2 million or more lines of code, we did not implement all functionality. After all, for the operations that libflame supports we usually have multiple algorithms where LAPACK only has one choice (one blocked and one unblocked). This was simply to great of a task even for someone with Field’s prowess. The good news is that libflame has simply continued to exist without a need for maintenance. An exceptional piece of software engineering that demonstrates the benefits of building on solid theory. A half dozen years ago, Kyungjoo Kim merged the netlib LAPACK code base in with the core libflame code, thus achieving full LAPACK functionality. As you now find out, such functionality does not automatically update itself as LAPACK releases changes. The Householder transformation-based code in libflame is the trickiest part. We use a variant on the WY transform that we call the UT transform [1]. This is the transform that accumulates multiple Householder transformations and then applies them so that matrix-matrix multiplication can be employed. There are two reasons why this is a superior solution: one, it avoid the inversion of a triangular matrix, which makes it more elegant and possibly more numerically stable. The second is that LAPACK views the case where the Householder transformation does not need to introduce zeros (because they are already there or because that part of the current column is already zero) as a special case where instead of using a Householder transformation is uses an identity. While on the surface this makes sense, in practice it causes “fringe” problems that prevent the use of the UT transform and certain (slight) optimizations. The bottom line: LAPACK got a detail wrong. Libflame fixes it. The annoying side-effect of this is that for a square matrix, the very last entry in the result matrix equals the negative of what LAPACK computes. The problem is in then interfacing the LAPACK interface to libflame. Kyungjoo took care of this, but it appears that now great care must be taken to insert new functionality. It may be that the new functionality involves a change in LAPACK’s test suite rather than in its base code. Given that the UT-Austin team is way too busy with BLIS to go back to looking at this, I see a number of possibilities: - It may be that Kyungjoo has time to advise. I am copying this message to him. - You may want to disable the use of all QR factorization related functionality that is provided through libflame and simply have the LAPACK code take care of that. - Modify the test suite so it tests for the result that libflame computes. - Ignore the failures. On Sep 14, 2020, at 7:15 AM, srvasanth <notifications@github.com<mailto:notifications@github.com>> wrote: Thank you for the reply Mr. Field. Currently I am in the process of adding LAPACK-3.9.0 updates into libFLAME. For this, the new and updated functionalities from LAPACK have been converted to C using f2c tool. Here, there are similar failures in single/double precision variants of QR, BD (SVD problems), SG (Symmetric Generalized Eigenvalue problems) test cases when tested using LAPACK-3.9.0 test suite. All these test cases call the Householder transformation functions. Can these failures also be considered as false failures? — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub<#40 (comment)>, or unsubscribe<https://github.com/notifications/unsubscribe-auth/ABLLYJ2KSUT7G3XRNZ3YLM3SFYCPFANCNFSM4Q7Z6JOQ>.

[srvasanth]

Thank you Dr. Robert for taking time to address the issue.
I will try to understand the additional functionalities added by lapack 3.9.0 version to see if any functionality as mentioned by Kyungjoo is indeed the cause of failures. Based on that understanding, I will check if one of your suggestions can be taken for further course of action.
Thank you.