# Algorithm to extract linearly dependent columns in a large scale [-1,1] matrix ( 10^5 by 10^6)

조회 수: 7 (최근 30일)
Wayne Shanks 2023년 1월 3일
답변: Joss Knight 2023년 1월 7일
I am trying to find an efficient algorithm for extracting linear independent collumns ( an old problem) but on a Very large matrix ( 10^5 rows, 10^6 columns) with all +-1 Real elements.... so , a dense matrix.
these matrcies are so large that I have no hope to put them in memory all at once, and then use the standard QR algorithm (or other real matrix decompositions that I have found) .
I know the choice of spanning collumns are not unique. I just want a subset "Q" of N colums of the Matrix A, such that rank(A) = N = rank(Q)
I have been looking for a clever random algorithm with bounded error.
Cheers
##### 댓글 수: 5이전 댓글 3개 표시이전 댓글 3개 숨기기
Wayne Shanks 2023년 1월 4일
I store these matricies as blocks of binary files, When I load them into memory to process , I convert the [0,1] bts to [-1,1] single floats
I am starting to read some articles on "out of core SVD" algorithms,
Bruno Luong 2023년 1월 4일
편집: Bruno Luong 2023년 1월 4일
SVD cannot find independent set of columns, QR does.
Do not use Gram Schmidt, it is numerically unstable. Use Housholder, and Q-less QR algorithm with permutation, until the projection is numerically 0.
But still storing R required few hundred Gb. It is doable on HD but it will take very long to compute.

댓글을 달려면 로그인하십시오.

### 답변 (1개)

Joss Knight 2023년 1월 7일
You might consider using distributed arrays on an HPC cluster.

댓글을 달려면 로그인하십시오.

### 카테고리

Help CenterFile Exchange에서 Linear Algebra에 대해 자세히 알아보기

### Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by