Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Regarding additional feature on Incremental SVD over available SVD_COMPRESSED method. #11527

Open
localhost-server opened this issue Nov 15, 2024 · 6 comments
Open

Regarding additional feature on Incremental SVD over available SVD_COMPRESSED method. #11527

localhost-server opened this issue Nov 15, 2024 · 6 comments
Labels
array enhancement Improve existing functionality or make things work better good second issue Clearly described, educational, but less trivial than "good first issue".

Comments

@localhost-server
Copy link

Hi, @hendrikmakait and other teams members,
I am working on implementation of DeepLearning Models using SVD specifically SVD_Compressed method available in Dask using dask.array.linalg.svd_compressed especially using CuPy to compute larger SVD matrix on GPUs. But there is a problem I am facing while implementing this. While Computing SVD on larger matrix which are not possible to get loaded fully on GPU memory at a time, we require something called incremental SVD in addition to SVD_Compressed. I know this is possible to be done and not too tough to be implemented if we already have SVD_Compressed running on GPU already. By this what I actually require to do is Distributed Streaming SVD computation on larger dataset which is available on Storage but not fully loaded on GPU.
@github-actions github-actions bot added the needs triage Needs a response from a contributor label Nov 15, 2024
@phofl
Copy link
Collaborator

phofl commented Nov 15, 2024

@dask/gpu

@phofl phofl added array gpu and removed needs triage Needs a response from a contributor labels Nov 15, 2024
@jacobtomlinson jacobtomlinson added the enhancement Improve existing functionality or make things work better label Nov 18, 2024
@jacobtomlinson
Copy link
Member

I don't necessarily think this is a GPU issue. It sounds like there is a problem with some intermediate step of the SVD taking up more memory than is available. GPUs typically have less memory than the host and so you're likely to run into this limit more quickly.

It sounds like what we want here is a more memory efficient implementation of SVD generally.

@localhost-server
Copy link
Author

I think you are right @jacobtomlinson , this is not a GPU problem, there must be some issue with Dask SVD_compressed method so it's not able to compute SVD of a matrix after a certain limit of single GPU or say GPU clusters. But I think , making development on this thing is very necessary to do to test Distributed Streaming SVD computation on larger dataset which is available on Storage but not fully loaded on GPU. Kindly guide like how it can be resolved , after it gets solved we will have very sharp edge in AI model building with dask gaining popularity.

@jacobtomlinson
Copy link
Member

The implementation is here. Do you have any interest in making improvements?

dask/dask/array/linalg.py

Lines 748 to 834 in 966bdb5

def svd_compressed(
a,
k,
iterator="power",
n_power_iter=0,
n_oversamples=10,
seed=None,
compute=False,
coerce_signs=True,
):
"""Randomly compressed rank-k thin Singular Value Decomposition.
This computes the approximate singular value decomposition of a large
array. This algorithm is generally faster than the normal algorithm
but does not provide exact results. One can balance between
performance and accuracy with input parameters (see below).
Parameters
----------
a: Array
Input array
k: int
Rank of the desired thin SVD decomposition.
iterator: {'power', 'QR'}, default='power'
Define the technique used for iterations to cope with flat
singular spectra or when the input matrix is very large.
n_power_iter: int, default=0
Number of power iterations, useful when the singular values
decay slowly. Error decreases exponentially as `n_power_iter`
increases. In practice, set `n_power_iter` <= 4.
n_oversamples: int, default=10
Number of oversamples used for generating the sampling matrix.
This value increases the size of the subspace computed, which is more
accurate at the cost of efficiency. Results are rarely sensitive to this choice
though and in practice a value of 10 is very commonly high enough.
compute : bool
Whether or not to compute data at each use.
Recomputing the input while performing several passes reduces memory
pressure, but means that we have to compute the input multiple times.
This is a good choice if the data is larger than memory and cheap to
recreate.
coerce_signs : bool
Whether or not to apply sign coercion to singular vectors in
order to maintain deterministic results, by default True.
Examples
--------
>>> u, s, v = svd_compressed(x, 20) # doctest: +SKIP
Returns
-------
u: Array, unitary / orthogonal
s: Array, singular values in decreasing order (largest first)
v: Array, unitary / orthogonal
References
----------
N. Halko, P. G. Martinsson, and J. A. Tropp.
Finding structure with randomness: Probabilistic algorithms for
constructing approximate matrix decompositions.
SIAM Rev., Survey and Review section, Vol. 53, num. 2,
pp. 217-288, June 2011
https://arxiv.org/abs/0909.4061
"""
comp = compression_matrix(
a,
k,
iterator=iterator,
n_power_iter=n_power_iter,
n_oversamples=n_oversamples,
seed=seed,
compute=compute,
)
if compute:
comp = comp.persist()
wait(comp)
a_compressed = comp.dot(a)
v, s, u = tsqr(a_compressed.T, compute_svd=True)
u = comp.T.dot(u.T)
v = v.T
u = u[:, :k]
s = s[:k]
v = v[:k, :]
if coerce_signs:
u, v = svd_flip(u, v)
return u, s, v

@localhost-server
Copy link
Author

@jacobtomlinson dask/dask/array/linalg.py Thank you for sharing this. I have checked this file before. But it lacks a feature, like suppose we have a matrix of shape AxB which is already very big like it takes a month to compute svd of such matrix and we computed SVD of this matrix but after we have a new matrix of shape (A+C)x(B+D) where we have same data as we had previously in matrix AxB. But as you know that we already have computed SVD for AxB matrix ,I want to use this computed value to find the SVD of this new data (A+C)x(B+D) . That's why it is being called Incremental SVD . So we don't have to compute SVD on entire data, DASK have this thing already implemented but seem like developers haven't included the API for this to be used. Kindly assist us bringing such feature.

@jacobtomlinson jacobtomlinson added the good second issue Clearly described, educational, but less trivial than "good first issue". label Nov 18, 2024
@exitflynn
Copy link

hello, i would like to try contributing a fix for the issue! 🤠

DASK have this thing already implemented but seem like developers haven't included the API for this to be used.

I tried looking around for the relevant parts of the codebase and I could only find the svd and the svd_compressed functions. I wasn't able to find any implementation that could directly be exposed to the API so I think this will still require doing some work for performing the incremental SVD, right? (let me know in case I missed something)

And in that case, it should require adding the incremental support for both the compressed as well as the regular SVDs, right?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
array enhancement Improve existing functionality or make things work better good second issue Clearly described, educational, but less trivial than "good first issue".
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
4 participants
@jacobtomlinson @exitflynn @phofl @localhost-server