Joss-reviews: [REVIEW]: HODLRlib: A Library for Hierarchical Matrices

Created on 12 Jan 2019 · 82Comments · Source: openjournals/joss-reviews

Submitting author: @sivaramambikasaran (Sivaram Ambikasaran)
Repository: https://github.com/sivaramambikasaran/HODLR
Version: v3.1415.1
Editor: @jedbrown
Reviewer: @poulson
Archive: 10.5281/zenodo.2561575

Status

Status badge code:

HTML: <a href="http://joss.theoj.org/papers/13a04e93261c02391266de3566257e15"><img src="http://joss.theoj.org/papers/13a04e93261c02391266de3566257e15/status.svg"></a>
Markdown: [![status](http://joss.theoj.org/papers/13a04e93261c02391266de3566257e15/status.svg)](http://joss.theoj.org/papers/13a04e93261c02391266de3566257e15)

Reviewers and authors:

Please avoid lengthy details of difficulties in the review thread. Instead, please create a new issue in the target repository and link to those issues (especially acceptance-blockers) in the review thread below. (For completists: if the target issue tracker is also on GitHub, linking the review thread in the issue or vice versa will create corresponding breadcrumb trails in the link target.)

Reviewer instructions & questions

@poulson, please carry out your review in this issue by updating the checklist below. If you cannot edit the checklist please:

Make sure you're logged in to your GitHub account
Be sure to accept the invite at this URL: https://github.com/openjournals/joss-reviews/invitations

The reviewer guidelines are available here: https://joss.theoj.org/about#reviewer_guidelines. Any questions/concerns please let @jedbrown know.

✨ Please try and complete your review in the next two weeks ✨

Review checklist for @poulson

Conflict of interest

[x] As the reviewer I confirm that I have read the JOSS conflict of interest policy and that there are no conflicts of interest for me to review this work.

Code of Conduct

[x] I confirm that I read and will adhere to the JOSS code of conduct.

General checks

[x] Repository: Is the source code for this software available at the repository url?
[x] License: Does the repository contain a plain-text LICENSE file with the contents of an OSI approved software license?
[x] Version: v3.1415.1
[x] Authorship: Has the submitting author (@sivaramambikasaran) made major contributions to the software? Does the full list of paper authors seem appropriate and complete?

Functionality

[x] Installation: Does installation proceed as outlined in the documentation?
[x] Functionality: Have the functional claims of the software been confirmed?
[x] Performance: If there are any performance claims of the software, have they been confirmed? (If there are no claims, please check off this item.)

Documentation

[x] A statement of need: Do the authors clearly state what problems the software is designed to solve and who the target audience is?
[x] Installation instructions: Is there a clearly-stated list of dependencies? Ideally these should be handled with an automated package management solution.
[x] Example usage: Do the authors include examples of how to use the software (ideally to solve real-world analysis problems).
[x] Functionality documentation: Is the core functionality of the software documented to a satisfactory level (e.g., API method documentation)?
[x] Automated tests: Are there automated tests or manual steps described so that the function of the software can be verified?
[x] Community guidelines: Are there clear guidelines for third parties wishing to 1) Contribute to the software 2) Report issues or problems with the software 3) Seek support

Software paper

[x] Authors: Does the paper.md file include a list of authors with their affiliations?
[x] A statement of need: Do the authors clearly state what problems the software is designed to solve and who the target audience is?
[x] References: Do all archival references that should have a DOI list one (e.g., papers, datasets, software)?

accepted published recommend-accept review

Source

whedon

Most helpful comment

@labarba @poulson @jedbrown Thanks for this wonderful journal and open review process!

sivaramambikasaran on 13 Feb 2019

❤2

All 82 comments

Hello human, I'm @whedon, a robot that can help you with some common editorial tasks. @poulson it looks like you're currently assigned as the reviewer for this paper :tada:.

:star: Important :star:

If you haven't already, you should seriously consider unsubscribing from GitHub notifications for this (https://github.com/openjournals/joss-reviews) repository. As a reviewer, you're probably currently watching this repository which means for GitHub's default behaviour you will receive notifications (emails) for all reviews 😿

To fix this do the following two things:

Set yourself as 'Not watching' https://github.com/openjournals/joss-reviews:

watching

You may also like to change your default settings for this watching repositories in your GitHub profile here: https://github.com/settings/notifications

notifications

For a list of things I can do to help you, just type:

@whedon commands

whedon on 12 Jan 2019

Attempting PDF compilation. Reticulating splines etc...

whedon on 12 Jan 2019

:point_right: Check article proof :page_facing_up: :point_left:

whedon on 12 Jan 2019

@poulson :wave: Welcome and thanks for agreeing to review! The comments from @whedon above outline the review process, which takes place in this thread (possibly with issues filed in the HODLRlib repository). I'll be watching this thread if you have any questions.

jedbrown on 12 Jan 2019

🎉1

I have filed https://github.com/sivaramambikasaran/HODLR/issues/22 to suggest install.sh downloading a more recent version of CMake since the current choice does not support all of the features needed by the project (i.e., add_compile_definitions).

poulson on 13 Jan 2019

@poulson These have now been addressed.

sivaramambikasaran on 14 Jan 2019

@whedon commands

sivaramambikasaran on 14 Jan 2019

Here are some things you can ask me to do:

# List Whedon's capabilities
@whedon commands

# List of editor GitHub usernames
@whedon list editors

# List of reviewers together with programming language preferences and domain expertise
@whedon list reviewers

# Compile the paper
@whedon generate pdf

whedon on 14 Jan 2019

@whedon generate pdf

sivaramambikasaran on 14 Jan 2019

Attempting PDF compilation. Reticulating splines etc...

whedon on 14 Jan 2019

:point_right: Check article proof :page_facing_up: :point_left:

whedon on 14 Jan 2019

@sivaramambikasaran Thank you for fixing that issue; I have verified that a from-scratch usage of install.sh now builds the library! (Though I had to manually install dvipng.)

I am now noticing that running a standard build and then executing ./tutorial leads to a segfault. It seems that one must manually specify the matrix height (N), leaf cutoff size (M), off-diagonal block rank (dim), and -log10(tolerance) as the first 4 arguments to tutorial to avoid a segfault. I would recommend using default versions of these parameters (or exiting with an error message) rather than segfaulting (and perhaps making note in the installation notes next to the cmake instructions).

I am also wondering what the recommended example is, as the runtimes for HODLR seem to be significantly slower than dense linear algebra up to a matrix dimension of 4000. For example:

~/Source/JOSS/HODLR/build-full$ ./tutorial 4000 128 10 12
========================= Problem Parameters =========================
Matrix Size                        :4000
Leaf Size                          :128
Number of Levels in Tree           :4
Dimensionality                     :10
Tolerance                          :1e-12

========================= Assembly Time =========================
Time for assembly in HODLR form    :37.7604
Time for direct matrix generation  :0.513778
Magnitude of Speed-Up              :0.0136063

========================= Matrix-Vector Multiplication =========================
Time for MatVec in HODLR form      :0.0915819
Time for direct MatVec             :0.0725777
Magnitude of Speed-Up              :0.79249
Error in the solution is           :3.47459e-16

========================= Factorization =========================
Time to factorize HODLR form       :39.0081
Time for LU Factorization          :6.82005
Magnitude of Speed-Up              :0.174837

========================= Solving =========================
Time to solve HODLR form           :0.195398
Time taken to solve exactly        :0.0639205
Magnitude of Speed-Up              :0.32713
Forward Error(HODLR)               :4.66641e-16
Forward Error(Exact)               :5.74886e-16
Backward Error(HODLR)              :4.19436e-16
Backward Error(Exact)              :5.5721e-16

========================= Determinant Computation =========================
Time taken for HODLR form          :0.0341471
Calculated Log Determinant(HODLR)  :9165.94
Calculated Log Determinant(Exact)  :9165.94
Relative Error in computation      :1.02141e-14

As an aside, it seems that all uppercase variable names are being used in the HODLR_Tree::plotTree and one of these is shadowing the C FILE keyword. (I am curious: how portable is the direct system call?) With that said, the generated images are quite informative!

I am also doing my best not to veer into anything approaching a code review, but I would recommend not incorporating any using statements (e.g., using std::cout;) outside of a custom namespace in your header files.

EDIT: I now realize that you are using a random matrix, so that the rank will be very high. I would recommend using your Gaussian random kernel example for your tutorial so that the user gets to see a speedup (the ultimate point of HODLR) as soon as possible.

poulson on 19 Jan 2019

@poulson Thanks. Our replies are inline.

I am now noticing that running a standard build and then executing ./tutorial leads to a segfault. It seems that one must manually specify the matrix height (N), leaf cutoff size (M), off-diagonal block rank (dim), and -log10(tolerance) as the first 4 arguments to tutorial to avoid a segfault. I would recommend using default versions of these parameters (or exiting with an error message) rather than segfaulting (and perhaps making note in the installation notes next to the cmake instructions).

This has been done. Unless all the four arguments are now passed, default arguments are used. Also, these arguments are relevant only for this specific example/tutorial file as has been mentioned here.

Further, the dim variable (i.e., the third input parameter) is not the off-diagonal rank. It is the dimension of the underlying data (Note that this is only needed for this tutorial file or in cases where the underlying matrix arises out of a kernel function and you need to sort the points in the appropriate dimension to get good low rank structure in the off-diagonal blocks). The ranks of the off-diagonal blocks are dictated by the tolerance, i.e., the fourth argument.

I am also wondering what the recommended example is, as the runtimes for HODLR seem to be significantly slower than dense linear algebra up to a matrix dimension of 4000. For example:

```
~/Source/JOSS/HODLR/build-full$ ./tutorial 4000 128 10 12

The reason for no speed up is that in the above case, the underlying dimension of the data is 10 and it turns out that the off-diagonal blocks are full rank. We suggest trying a lower dimension (say 1 or 2 for the current tutorial file). When the off-diagonal blocks are full-rank, our code will take a longer time than the usual LU, since our code tries to compress these full-rank off-diagonal blocks in the first place and also relies on a different factorization.

As an aside, it seems that all uppercase variable names are being used in the HODLR_Tree::plotTree and one of these is shadowing the C FILE keyword. (I am curious: how portable is the direct system call?) With that said, the generated images are quite informative!

All variable names have been changed to lower-case in line with the rest of the code. The system command seems to work on the systems we have tested so far (Ubuntu 18.10, 16.04 and also on Mac Mojave 10.14.1).

I am also doing my best not to veer into anything approaching a code review, but I would recommend not incorporating any using statements (e.g., using std::cout;) outside of a custom namespace in your header files.

This has now been fixed for cout and endl. We still rely on using for setting the datatype used in the code (i.e., float or double or complex32 or complex64).

EDIT: I now realize that you are using a random matrix, so that the rank will be very high. I would recommend using your Gaussian random kernel example for your tutorial so that the user gets to see a speedup (the ultimate point of HODLR) as soon as possible.

As mentioned above, we use the Gaussian kernel on a random set of points. Just that the dimension was high, it resulted in full-rank off-diagonal blocks for these "small" matrices. We have used a random matrix as part of /test/test_HODLR.cpp to ensure that our solver is robust even for a random matrix with full-rank off-diagonal blocks.

sivaramambikasaran on 21 Jan 2019

👍1

@sivaramambikasaran Unfortunately, that changeset broke the other examples, e.g., examples/example.cpp (namely, they were expecting std::cout to be imported into the global namespace). Along this line, is there a reason for forcing CMake to only build one executable for each configuration? I would highly recommend building all of the examples and tests with the default configuration; it would make it much easier for users (and myself) to explore the functionality and make sure everything builds.

poulson on 21 Jan 2019

@poulson We have now fixed the other examples and the CMake builds all the examples and test files. Thanks.

sivaramambikasaran on 22 Jan 2019

Thanks @sivaramambikasaran! It seems the only item left is clarifying what the recommended means of users contributing to the software is. To some degree, this is implicit in the GitHub model, but it would be good to have an explicit statement of the recommended process.

poulson on 30 Jan 2019

@poulson We have now added CONTRIBUTING.md file. Let us know if you would like us to add more information in that file.

sivaramambikasaran on 1 Feb 2019

@jedbrown I recommend the package for publication.

poulson on 1 Feb 2019

👍1

@sivaramambikasaran Can you add a DOI for the published paper? Would it make sense to include any citations to related work (software or otherwise) to compare capability, scope, and the like?

in these articles[@ambikasaran2013mathcal][@ambikasaran2014fast].

should probably be

in @ambikasaran2013mathcal and @ambikasaran2014fast.

You can remove the link to the repository; that information will be in template. Also, I think your wild escapes are causing Pandoc to eat the title of the paper. Does normal math syntax not work?

jedbrown on 2 Feb 2019

@whedon generate pdf

sivaramambikasaran on 4 Feb 2019

Attempting PDF compilation. Reticulating splines etc...

whedon on 4 Feb 2019

:point_right: Check article proof :page_facing_up: :point_left:

whedon on 4 Feb 2019

@whedon generate pdf

sivaramambikasaran on 4 Feb 2019

Attempting PDF compilation. Reticulating splines etc...

whedon on 4 Feb 2019

:point_right: Check article proof :page_facing_up: :point_left:

whedon on 4 Feb 2019

@jedbrown Our replies are inline.

@sivaramambikasaran Can you add a DOI for the published paper?

Done.

Would it make sense to include any citations to related work (software or otherwise) to compare capability, scope, and the like?

While our library has some similarity with other libraries such as STRUMPACK and H2Lib, each works on a different structure and comparisons among them would be difficult to evaluate.

in these articles[@ambikasaran2013mathcal][@ambikasaran2014fast].

should probably be

in @ambikasaran2013mathcal and @ambikasaran2014fast.

Done.

You can remove the link to the repository; that information will be in template.

Done.

Also, I think your wild escapes are causing Pandoc to eat the title of the paper. Does normal math syntax not work?

We tried compiling using pandoc from markdown to LaTeX and it seems to work fine. The article generated by whedon also shows the title. So we don't quite understand where/how the title of the paper is eaten.

sivaramambikasaran on 4 Feb 2019

Thanks. I believe the above commit will fix the bib formatting. Notice that the title of that paper was not shown in the bib.

Regarding comparison, it doesn't need to be quantitative, but I think it would be useful to write a short paragraph explaining what this package offers that others don't/why someone would choose yours, and any known limitations. A potential user shouldn't need to read between the lines to obtain such information. Does that seem reasonable to add? Thanks.

jedbrown on 4 Feb 2019

@whedon generate pdf

jedbrown on 4 Feb 2019

Attempting PDF compilation. Reticulating splines etc...

whedon on 4 Feb 2019

:point_right: Check article proof :page_facing_up: :point_left:

whedon on 4 Feb 2019

The bib entry looks good now. Can you let me know if you are willing to write a short paragraph to help potential users make appropriate decisions on when to use your software versus other packages? Thanks.

jedbrown on 4 Feb 2019

@whedon generate pdf

sivaramambikasaran on 5 Feb 2019

Attempting PDF compilation. Reticulating splines etc...

whedon on 5 Feb 2019

:point_right: Check article proof :page_facing_up: :point_left:

whedon on 5 Feb 2019

@jedbrown We have added info as per your suggestion. There are couple of more things to be added still. We should have it done within the next few hours. Will ping you once we are done.

sivaramambikasaran on 5 Feb 2019

Attempting PDF compilation. Reticulating splines etc...

whedon on 5 Feb 2019

:point_right: Check article proof :page_facing_up: :point_left:

whedon on 5 Feb 2019

Attempting PDF compilation. Reticulating splines etc...

whedon on 5 Feb 2019

:point_right: Check article proof :page_facing_up: :point_left:

whedon on 5 Feb 2019

@whedon generate pdf

sivaramambikasaran on 5 Feb 2019

Attempting PDF compilation. Reticulating splines etc...

whedon on 5 Feb 2019

:point_right: Check article proof :page_facing_up: :point_left:

whedon on 5 Feb 2019

@jedbrown We are done now (hopefully). One little thing is I do not know how to get doi of a thesis. Also, we have cited a SIAM LA presentation. Hopefully this is fine as well.

sivaramambikasaran on 5 Feb 2019

There's a bib formatting issue, described here. https://github.com/sivaramambikasaran/HODLR/commit/1bef70dbf42d1748ab2471463eb46e2b14cadd7d

"Hierachical" is misspelled.

Looks good otherwise; thanks for this further explanation.

jedbrown on 6 Feb 2019

@whedon check references

jedbrown on 6 Feb 2019

Attempting to check references...

whedon on 6 Feb 2019

```Reference check summary:

OK DOIs

http://doi.org/10.1007/s10915-013-9714-z is OK
http://doi.org/10.1007/s006070050015 is OK
http://doi.org/10.1007/s006070050002 is OK
http://doi.org/10.1007/s00607-002-1450-4 is OK
http://doi.org/10.1137/S0895479803436652 is OK
http://doi.org/10.1137/16M1087278 is OK
http://doi.org/10.1088/1402-4896/aae34e is OK
http://doi.org/10.1109/TPAMI.2015.2448083 is OK
http://doi.org/10.1137/15M1010117 is OK

MISSING DOIs

https://doi.org/10.2172/963444 may be missing for title: Fast symmetric factorization of hierarchical matrices with applications

INVALID DOIs

None
```

whedon on 6 Feb 2019

:point_up: Experimental feature gets that missing DOI wrong.

jedbrown on 6 Feb 2019

@jedbrown

There's a bib formatting issue, described here. sivaramambikasaran/HODLR@1bef70d

Done

"Hierachical" is misspelled.

Fixed

Looks good otherwise; thanks for this further explanation.

Hopefully, she can fly now.

sivaramambikasaran on 6 Feb 2019

@whedon generate pdf

sivaramambikasaran on 6 Feb 2019

Attempting PDF compilation. Reticulating splines etc...

whedon on 6 Feb 2019

:point_right: Check article proof :page_facing_up: :point_left:

whedon on 6 Feb 2019

@jedbrown Just pinging to check if anything needs to be done from our end.

sivaramambikasaran on 8 Feb 2019

Please consider this PR, then tag a release (annotated tag preferred) and archive on Zenodo or similar.

https://github.com/sivaramambikasaran/HODLR/pull/37

jedbrown on 8 Feb 2019

@jedbrown

Please consider this PR,

Done

then tag a release (annotated tag preferred)

Done; See here: https://github.com/sivaramambikasaran/HODLR/releases/tag/v3.1415.1

and archive on Zenodo or similar.

Done

See here: https://zenodo.org/record/2561575#.XGETt88zYW8

DOI: 10.5281/zenodo.2561575