Repository: pytorch
Issue: Triangular solver for sparse matrices
Labels: module: sparse,triaged,module: linear algebra

### 🚀 The feature, motivation and pitch

Despite not being explicitly documented, [`torch.triangular_solve`](https://pytorch.org/docs/stable/generated/torch.triangular_solve.html) appears to support sparse matrices in CSR and BSR format.

`torch.triangular_solve` is marked deprecated in favour of [`torch.linalg.solve_triangular`](https://pytorch.org/docs/stable/generated/torch.linalg.solve_triangular.html). However `torch.linalg.solve_triangular` does not seem to currently support sparse matrices.

It woud be great to have at least feature parity between `torch.triangular_solve` and `torch.linalg.solve_triangular`. It would also be very helpful to document the existing support for sparse matrices. I indeed only incidentally found out about `torch.triangular_solve` supporting BSR inputs when reading about it in an issue https://github.com/pytorch/pytorch/issues/9222#issuecomment-1006591190. I then found out about CSR support by "random" trial and error.

Additionally, the gradient computed using `torch.triangular_solve` is dense whcih is unexpected. The gradient with respect to the non-zero values only would be more in line with other sparse ops. 

### Alternatives

Alternative 1: Relying on the deprecated function until it gets removed

Alternative 2: Implementing a workaround through [`cupyx.scipy.sparse.linalg.spsolve_triangular`](https://docs.cupy.dev/en/stable/reference/generated/cupyx.scipy.sparse.linalg.spsolve_triangular.html) and a custom backward op similar to what I suggested here for generic sparse matrices:
https://github.com/pytorch/pytorch/issues/69538#issuecomment-1010956880

### Additional context

Related issues include: pytorch/pytorch#53441 pytorch/pytorch#9222 pytorch/pytorch#69538 pytorch/pytorch#28341 pytorch/pytorch#10043 pytorch/pytorch#87085

Rough test script:
```python
# Try with the nightly version of PyTorch
!pip3 install --pre torch torchvision torchaudio torchtext --extra-index-url https://download.pytorch.org/whl/nightly/cu117 --upgrade

import torch
print(f'Running PyTorch version: {torch.__version__}')

torchdevice = torch.device('cpu')
if torch.cuda.is_available():
  torchdevice = torch.device('cuda')
  print('Default GPU is ' + torch.cuda.get_device_name(torch.device('cuda')))
print('Running on ' + str(torchdevice))

# Dimension of the square sparse matrix
n = 5
# Number of non-zero elements (up to duplicates)
nnz = 8

rowidx = torch.randint(low=0, high=n, size=(nnz,), device=torchdevice)
colidx = torch.randint(low=0, high=n, size=(nnz,), device=torchdevice)
itemidx = torch.vstack((rowidx,colidx))
xvalues = torch.randn(nnz, dtype=torch.double, device=torchdevice)
x_coo = torch.sparse_coo_tensor(itemidx, xvalues, size=(n,n)).coalesce()
x_csr = x_coo.to_sparse_csr()

t_dense = torch.triu(x_coo.to_dense())+torch.eye(n,device=torchdevice)
t_coo = t_dense.to_sparse_coo()
t_csr = t_dense.to_sparse_csr()
t_bsr = t_csr.to_sparse_bsr(1)

b = torch.randn(n, dtype=torch.double, device=torchdevice).unsqueeze(1)

print('\ntorch.triangular_solve dense:\n===\n',torch.triangular_solve(b,t_dense,upper=True))
print('\ntorch.linalg.solve_triangular dense:\n===\n',torch.linalg.solve_triangular(t_dense,b,upper=True))

try:
  print('\ntorch.triangular_solve coo:\n===\n',torch.triangular_solve(b,t_coo,upper=True))
except Exception as err:
  print('\nException - torch.triangular_solve coo:\n===\n')
  print(Exception, err)
try:
  print('\ntorch.linalg.solve_triangular coo:\n===\n',torch.linalg.solve_triangular(t_coo,b,upper=True))
except Exception as err:
  print('\nException - torch.linalg.solve_triangular coo:\n===\n')
  print(Exception, err)

print('\ntorch.triangular_solve csr:\n===\n',torch.triangular_solve(b,t_csr,upper=True))
try:
  print('\ntorch.linalg.solve_triangular csr:\n===\n',torch.linalg.solve_triangular(t_csr,b,upper=True))
except Exception as err:
  print('\nException - torch.linalg.solve_triangular csr:\n===\n')
  print(Exception, err)

print('\ntorch.triangular_solve bsr:\n===\n',torch.triangular_solve(b.unsqueeze(0),t_bsr,upper=True))
try:
  print('\ntorch.triangular_solve bsr:\n===\n',torch.linalg.solve_triangular(t_bsr,b,upper=True))
except Exception as err:
  print('\nException - torch.triangular_solve bsr:\n===\n')
  print(Exception, err)

try:
  tt_csr= t_csr.detach().clone().requires_grad_(True)
  bb = b.detach().clone().requires_grad_(True)
  test = torch.autograd.gradcheck(torch.triangular_solve, (bb,tt_csr), check_sparse_nnz=True, eps=1e-6, atol=1e-4)
  print('\n=\ncsr torch.triangular_solve',test)
except Exception as err:
  print('\n=\ncsr torch.triangular_solve except')
  print(Exception, err)
```

cc @nikitaved @pearu @cpuhrsch @amjames @bhosmer @jianyuh @mruberry @walterddr @IvanYashchuk @xwang233 @Lezcano