Skip to content

Version 0.2

Jump to bottom
Nathaniel Pritchard edited this page Feb 1, 2025 · 15 revisions

The following lays out the development plan for version 0.2. To help manage workload we will have the following point system where any individual will not be doing any more than 4 points of work in a week. First for revisions the points are as follows:

Point Description
2 A PR whose main file more than 2 pairs of data structures
1 A PR whose main file has 2 data structures or 2nd revision of 2 point PR
0.5 A 2nd revision of a 1 point PR or 3rd revision of 2 point PR or Small abstract type PR

Beyond the first increment each subsequent increment will focus on implementing all similar techniques at once to make the review process more consistent and efficient. The goal of these implementations, should result in the library approximately subsuming most of the core functionality of version 0.1 by version 0.2.2.

Version 0.2.1

The first incrementation of version 0.2.1 will be made when we have built the basics of what is currently in version 0.1. Specifically, we will have built:

Solvers Approximators Compressors Loggers SubSolvers
1. Row_Projection(Kaczmarz Solver)
2. Col_Projection (Coordinate Descent)		 1. Random RangeFinder (Randomized QR)
2. Randomized SVD		 1. Sparse Sign
2. Gaussian		 1. Basic Logger
2. MA Logger		 1. LQ Solver
2. QR Solver

Schedule for Version 0.2.1

Week Tasks completed PRs Reviewed
Feb 3 1. Abstract Types
2. Design Description		 None
Feb 10 1. Sparse Sign Compressor 1. Compressors (.5)
2. Approximators (.5)
3. Solvers (.5)
4. RLinearAlgebra (.5)
Feb 17 1. Basic Logger 1. SubSolvers (.5)
2. Loggers (.5)
3. SparseSign (2)
Feb 24 1. LQSubSolver 1. SpareSign (1)
2. BasicLogger (1)
Mar 3 1. KaczmarzSolver 1. SparseSign (.5)
2. BasicLogger (.5)
3. LQSubSolver (1)
Mar 10 1. QRSubSolver
2. GaussianCompressor		 1. KaczmarzSolver (2)
2. LQSubSolver (1)
Mar 17 1. CoordinateDescentSolver
2. RangeFinder		 1. KaczmarzSolver (1)
2. QRSubSolver (1)
3. GaussianCompresssor (1)
4. LQSubSolver (.5)
Mar 24 1. MALogger 1. KaczmarzSolver (.5)
2. QRSubSolver (.5)
3. GaussianCompresssor (.5)
4. CoordinateDescentSolver (2)
5. RangeFinder (2)
Mar 31 1. RandomizedSVD 1. CoordinateDescentSolver (1)
2. RangeFinder (1)
3. MALogger (1)
April 7 Revisions 1. RandomizedSVD (1)
2. CoordinateDescentSolver(.5)
3. RangeFinder (.5)
4. MALogger (.5)
April 14 Revisions 1. RandomizedSVD (.5)

Version 0.2.1 Completed by April 21nd

Version 0.2.2

We will be able to increment when we have finished all the compressors.

Compressors

  1. CountSketch
  2. BlockFJLT
  3. CyclicSampling
  4. SamplingWithoutReplacement
  5. Sketch With Uniform entries
  6. AchlioptasSketch (Rademacher)
  7. BlockSRHT
Week Tasks completed PRs Reviewed
April 21 1. Sketch With Uniform entries
2. BlockFJLT
3. Revisions		 None
April 28 1. CyclicSampling
2. SamplingWithoutReplacement
3. Revisions		 1. Sketch With Uniform entries (1)
2. BlockFJLT (1)
May 5 1. AchlioptasSketch
2. FJLT
3. Revisions		 1. Sketch With Uniform entries (.5)
2. BlockFJLT (.5)
3. CyclicSampling (1)
4. SamplingWithoutReplacement (1)
May 12 1. CyclicSampling
2. CountSketch
3. Revisions		 1. CyclicSampling (.5)
2. SamplingWithoutReplacement (.5)
3. AchlioptasSketch (1)
4. FJLT (1)
May 12 1. SRHT
2. Revisions		 1. AchlioptasSketch (.5)
2. FJLT (.5)
3. CyclicSampling (1)
4. CountSketch (1)
May 19 Revisions 1. CyclicSampling (.5)
2. CountSketch (.5)
3. SRHT (1)
May 26 Revisions 1. SRHT (.5)
June 2 Revisions Extra Week for Overages

Version 0.2.2 Completed by May 27th

Version 0.2.3

In version 0.2.3, we will fill out the CUR techniques in the approximators. This will require that we first create a general abstract CUR type. We then will iterative and single pass implementation of these methods. The user will be able to choose a column selection, row selection, pseudo inverse, refinement technique, and error technique.

Approximators

  1. LeverageScore
  2. Approximate LeverageScore
  3. Sketch and Pivot QR
  4. Sketch and Pivot LU
  5. Pivot LU
  6. Pivot QR
  7. Osinsky
  8. IterativeCUR
Week Tasks completed PRs Reviewed
June 9 1. CUR Structure None
June 16 1. Pivoted LU
2. Pivoted QR		 1. CUR Structure (2)
June 23 1. LeverageScore
2. Approximate LeverageScore		 1. CUR Structure (1)
2. Pivoted LU (1)
3. Pivoted QR (1)
June 30 Revisions 1. CUR Structure (.5)
2. Pivoted LU (.5)
3. Pivoted QR (.5)
4. LeverageScore (1)
5. Approximate LeverageScore (1)
July 6 1. IterativeCUR structure 1. LeverageScore (.5)
2. Approximate LeverageScore (.5)
July 13 1. Sketch and Pivot LU
2. Sketch and Pivot QR		 1. IterativeCUR structure (2)
July 20 1. Osinsky selection 1. IterativeCUR structure (1)
2. Sketch and Pivot LU (1)
3. Sketch and Pivot QR (1)
July 27 Revisions 1. IterativeCUR structure (.5)
2. Sketch and Pivot LU (.5)
3. Sketch and Pivot QR (.5)
August 4 Revisions Week to catch up

Version 0.2.3 Completed by August 4th

Version 0.2.4

Version 0.2.4 will focus on adding additional SubSolver techniques to the code base. These can be called by the row and block solver techniques. Each solver should have an implmentation that over-writes ldiv! from the LinearAlgebra library.

SubSolvers

  1. LU Solver
  2. Cholesky Solver
  3. Randomized Cholesky Solver
  4. LSQR
  5. LSMR
  6. CG
  7. BICGSTAB
  8. GMRES
Week Tasks completed PRs Reviewed
Aug 11 1. LU Solver
2. Cholesky Solver		 None
Aug 18 1. Randomized Cholesky
2. CG		 1. LU Solver (1)
2. Cholesky Solver (1)
Aug 25 1. LSQR
2. LSMR		 1. LU Solver (.5)
2. Cholesky Solver (.5)
3. Randomized Cholesky (1)
4. CG (1)
Sep 1 1. BICGSTAB
2. GMRES		 1. Randomized Cholesky (.5)
2. CG (.5)
3. LSQR (1)
4. LSMR (1)
Sep 8 Revisions 1. LSQR (.5)
2. LSMR (.5)
3. BICGSTAB (1)
4. GMRES (1)
Sep 15 Revisions 1. BICGSTAB (1)
2. GMRES (1)

Version 0.2.4 Completed by Sep 15th

Version 0.2.5

With the completion of the version 0.2.1, we will have implementations of the row and column projection methods. In version 0.2.5 we will expand the method available in the library for solving linear systems. These will follow a similar implementation pattern to the row and column projection methods of version 0.2.1.

Solvers

  1. Iterative Hessian Sketch
  2. Preconditioned Krylov (LSRN and Blendenpik)
  3. FOSSILS
  4. Sketch and Solve (Row Sketch and solve the sketched problem)
  5. Balabanov and Grigori Randomized Krylov
  6. Nakatsukasa and Tropp Randomized GMRES
Week Tasks completed PRs Reviewed
Sep 22 1. Iterative Hessian Sketch None
Sep 29 1. Preconditioned Krylov 1. IHHS (2)
Oct 6 1. FOSSILS 1. IHHS (1)
2. Preconditioned Krylov (2)
Oct 13 1. Sketch and Solve 1. IHHS (.5)
2. Preconditioned Krylov (1)
3. Fossils (2)
Oct 20 1. Balabanov and Grigori 1. Preconditioned Krylov (.5)
2. FOSSILS (1)
3. Sketch and Solve (2)
Oct 27 1. Nakatsukasa and Tropp 1. FOSSILS (.5)
2. Sketch and Solve (1)
3. Balabanov (2)
Nov 3 Revisions 1. Sketch and Solve (.5)
2. Balabanov (1)
3. Nakasukasa (2)
Nov 10 Revisions 1. Balabanov (.5)
Nakatsukasa (1)
Nov 17 Revisions 1. Nakatsukasa (.5)
Nov 24 Revisions Extra Week for revisions

Version 0.2.5 Completed by November 24th

Version 0.2.6

The final main set of implementations for version 0.2.6 will be the Nystrom approximations. The techniques that need to be implemented for this portion include RPCholesky, as well as others, but more research needs to be done to make a final determination of the overall techniques. The implementation design should be similar to that of the CUR techniques in version 0.2.3.

Approximators

  1. RPCholesky
  2. Uniform Column Selection
Week Tasks completed PRs Reviewed
Dec 1 1.Nystrom Structure None
Dec 8 1. RPCholesky 1. Nystrom (2)
Dec 15 1. Uniform Column Selection 1. Nystrom (1)
2. RPCholesky (1)
Dec 22 Revisions 1. Nystrom (.5)
2. RPCholesky (.5)
3. Uniform Selection (1)
Dec 29 Revisions 1. Uniform Selection (.5)

Version 0.2.6 Completed by December 29th

Clone this wiki locally