Repository: pytorch
Issue: Very big differences in output of `torch.lobpcg` (values and run-time) compared to SciPy on a very ill-conditioned Laplacian matrix
Labels: triaged,module: linear algebra

### 🐛 Describe the bug

The input matrix is dumped from https://www.vision.huji.ac.il/SpectralMatting/ octave code, and represents a matting laplacian matrix - very ill-conditioned, has 9 nonzero entries per row (smallest eigval of 0, largest eigenvalue of 9), a lot of very near-zero eigenvalues.

The output of torch.lobpcg seems much more correct than scipy.sparse.linalg.lobpcg, but very different :) And also much slower. Any ideas why this might happen? @lobpcg @pearu, maybe you would have an advice? I thought that torch.lobpcg was essentially a port of scipy.sparse.linalg.lobpcg, no? Is the default value of `tol` determined differently?

Is there anywhere an example of how such laplacian systems should be preconditioned?
- In https://github.com/scipy/scipy/issues/19235#issuecomment-1722516740 I noted that octave produces output much faster (despite that both SciPy and Octave use ARPACK under the hood).
- In https://github.com/scikit-learn/scikit-learn/blob/7f9bad99d6e0a3e8ddf92a7e5561245224dab102/sklearn/manifold/_spectral_embedding.py#L346 I found that scikit-learn applies LOBPCG on input with diag shifted by 1e-5 - but doing this does not improve the SciPy's output (the correct smallest eigvals are all ~0, not ~5)

[L_octave.mat.zip](https://github.com/pytorch/pytorch/files/12648072/L_octave.mat.zip)

```python
import time
import scipy
import numpy as np
import torch

eigs_num=50;

i, j, v, m, n = map(scipy.io.loadmat('L_octave.mat').get, ['i', 'j', 'v', 'm', 'n'])
i = i.squeeze(1).astype('int32') - 1
j = j.squeeze(1).astype('int32') - 1
v = v.squeeze(1).astype('float32')
m = int(m)
n = int(n)
print(i.shape, j.shape, v.shape, int(m), int(n))

L = scipy.sparse.coo_matrix((v, (i, j)), shape = (m, n))

np.random.seed(42)
X = np.random.normal(size=(m, eigs_num )).astype('float32')

tic = time.time()
eigval = scipy.sparse.linalg.eigsh(L, eigs_num, which='SM', return_eigenvectors=False)
print(eigval)
print('scipy.sparse.linalg.eigsh', time.time() - tic)

tic = time.time()
eigval, eigvec = scipy.sparse.linalg.lobpcg(L, X, maxiter = 1000, largest = False)
print(eigval)
print('scipy.sparse.linalg.logpcg', time.time() - tic)

tic = time.time()
eigval, eigvec = torch.lobpcg(torch.sparse_coo_tensor(torch.stack([torch.as_tensor(i), torch.as_tensor(j)]), torch.as_tensor(v), size = L.shape), X = torch.as_tensor(X), k = eigs_num, largest = False, niter = 1000)
print(eigval)
print('torch.lobpcg', time.time() - tic)
```

output:
```
(3188406,) (3188406,) (3188406,) 128400 128400
[4.5030788e-04 4.2453315e-04 4.1517158e-04 3.8193684e-04 3.8071713e-04
 3.4807756e-04 3.4010404e-04 3.2250569e-04 2.7762813e-04 2.7402333e-04
 2.6094113e-04 2.3607175e-04 2.2584437e-04 2.0594637e-04 2.0127479e-04
 1.9350117e-04 1.8327046e-04 1.7235774e-04 1.6348275e-04 1.5041916e-04
 1.4643844e-04 1.3529375e-04 1.2902766e-04 1.2850901e-04 1.2593951e-04
 1.0800803e-04 1.0034799e-04 9.7508135e-05 9.6017233e-05 8.9910092e-05
 8.8589368e-05 7.2698742e-05 7.0671063e-05 6.5970075e-05 6.1649480e-05
 5.8771104e-05 5.7743473e-05 5.7501289e-05 4.6025161e-05 4.5723471e-05
 4.1400210e-05 3.8752623e-05 3.6583613e-05 2.6378684e-05 2.2586199e-05
 1.6014528e-05 1.0540600e-05 9.0244203e-06 7.9671645e-06 6.7056526e-08]
scipy.sparse.linalg.eigsh 266.0989365577698
[5.5764084 5.5895004 5.5967197 5.599278  5.6036086 5.6075673 5.612417
 5.622675  5.6258216 5.627     5.629461  5.63777   5.641882  5.6433797
 5.6449986 5.648331  5.651633  5.6590447 5.659555  5.670805  5.6723266
 5.6753798 5.6767316 5.6811604 5.685404  5.688234  5.6918545 5.693018
 5.694217  5.7012777 5.703604  5.7075367 5.708476  5.712419  5.7155733
 5.717812  5.723774  5.728133  5.7328434 5.736811  5.7427206 5.7465687
 5.7523456 5.754298  5.7585073 5.7666636 5.7695017 5.772464  5.7793713
 5.783919 ]
scipy.sparse.linalg.logpcg 1.3224408626556396
tensor([8.7688e-05, 1.0392e-04, 1.1558e-04, 1.0228e-04, 1.0984e-04, 1.2023e-04,
        1.3466e-04, 1.4477e-04, 1.3094e-04, 1.3702e-04, 1.3840e-04, 1.5007e-04,
        1.2557e-04, 1.3130e-04, 1.4117e-04, 1.5102e-04, 1.5749e-04, 1.7784e-04,
        1.8517e-04, 1.8209e-04, 2.0007e-04, 1.8993e-04, 1.9568e-04, 2.1500e-04,
        2.1919e-04, 2.2342e-04, 2.3812e-04, 2.4824e-04, 2.8042e-04, 2.2152e-04,
        2.0526e-04, 2.2028e-04, 2.5449e-04, 2.8130e-04, 2.9647e-04, 3.0863e-04,
        3.4404e-04, 3.4340e-04, 3.7165e-04, 3.6539e-04, 4.2566e-04, 4.3179e-04,
        4.2837e-04, 3.1011e-04, 4.0076e-04, 4.4517e-04, 4.9045e-04, 5.1192e-04,
        5.5956e-04, 6.4424e-04])
torch.lobpcg 123.57711958885193
```

### Versions

 torch.__version__
'2.1.0.dev20230802+cpu'

scipy.__version__
'1.10.1'

np.__version__
'1.24.2'

cc @jianyuh @nikitaved @pearu @mruberry @walterddr @xwang233 @Lezcano