Content deleted Content added
m Replace template per TFD |
added basic CSR format implementation in c++, along with an example of how to use it Tag: Reverted |
||
Line 151:
It is likely known as the Yale format because it was proposed in the 1977 Yale Sparse Matrix Package report from Department of Computer Science at Yale University.<ref>{{cite web |url=https://apps.dtic.mil/dtic/tr/fulltext/u2/a047724.pdf |archive-url=https://web.archive.org/web/20190406045412/https://apps.dtic.mil/dtic/tr/fulltext/u2/a047724.pdf |url-status=live |archive-date=April 6, 2019 |title=Yale Sparse Matrix Package |last1=Eisenstat |first1=S. C. |last2=Gursky |first2=M. C. |last3=Schultz |first3=M. H. |last4=Sherman |first4=A. H. |date=April 1977 |language=English |access-date=6 April 2019 }}</ref>
====Basic Implementation====
This is a basic implementation of how a matrix could be stored in CSR format in C++. It contains some basic helper functions to improve usability.
Note that you can pass a tolerance parameter to it. Any values in the given matrix with absolute value smaller than or equal to this tolerance parameter will be considered to be zero. This can be useful when numerical instability is a concern, and numbers might be very close to zero when they should be zero
<syntaxhighlight lang="cpp">
struct CSR {
size_t rows, cols;
std::vector<float> values;
std::vector<size_t> col_idx, row_idx;
// m is expected to have at least one row and all its columns should have the same size
CSR(const std::vector<std::vector<float>>& m, float tol = 0.0f) : rows(m.size()), cols(m[0].size()), row_idx(std::vector<size_t>(rows + 1, 0)) {
for (size_t i = 0; i < rows; ++i) {
for (size_t j = 0; j < cols; ++j) {
// this ensures small enough elements can be considered zeros
if (std::abs(m[i][j]) <= tol) continue;
values.push_back(m[i][j]);
col_idx.push_back(j);
}
row_idx[i + 1] = values.size();
}
}
CSR(size_t m, size_t n) : rows(m), cols(n), row_idx(std::vector<size_t>(rows + 1, 0)) {}
// returns number of non-zero entries
size_t getNNZ() const {
return values.size();
}
float getDensity() const {
return (float) getNNZ() / (rows * cols);
}
float getSparsity() const {
return 1.0f - getDensity();
}
inline size_t getRowStart(size_t row) const {
return row_idx[row];
}
inline size_t getRowEnd(size_t row) const {
return row_idx[row + 1];
}
inline size_t getRowSize(size_t row) const {
return row_idx[row + 1] - row_idx[row];
}
// get index of n-th column with non-zero entry at given row
inline size_t getRowNthColumn(size_t row, size_t n) const {
return col_idx[getRowStart(row) + n];
}
// get value of n-th non-zero entry at given row
inline float getRowNthElement(size_t row, size_t n) const {
return values[getRowStart(row) + n];
}
void addElement(size_t row, size_t col, float elem) {
// insert element but keep col_idx sorted
size_t idx = std::distance(col_idx.begin(), std::lower_bound(col_idx.begin() + row_idx[row], col_idx.begin() + row_idx[row + 1], col));
// there already exists an element in this position. Just update its value
if (col_idx.size() > 0 && col_idx[idx] == col) {
values[idx] = elem;
return;
}
values.insert(values.begin() + idx, elem);
col_idx.insert(col_idx.begin() + idx, col);
// add 1 element to the row we are inserting (every row after it starts on element after)
for (size_t i = row + 1; i < row_idx.size(); ++i) {
++row_idx[i];
}
}
void updateElement(size_t row, size_t col, float val) {
size_t idx = std::distance(col_idx.begin(), std::lower_bound(col_idx.begin() + row_idx[row], col_idx.begin() + row_idx[row + 1], col));
values[idx] = val;
}
};
</syntaxhighlight>
An example of how to use this to perform a matrix-vector product follows:
<syntaxhighlight lang="cpp">
std::vector<float> multiplyMatVec(const CSR& mat, const std::vector<float>& vec) {
std::vector<float> result(mat.rows, 0.0f);
for (size_t i = 0; i < mat.rows; ++i) {
// iterate only over the non-zero entries in the i-th row of the matrix
for (size_t j = 0; j < mat.getRowSize(i); ++j) {
// multiply each non-zero element by the corresponding vector element and accumulate the result
result[i] += mat.getRowNthElement(i, j) * vec[mat.getRowNthColumn(i, j)];
}
}
return result;
}
</syntaxhighlight>
===Compressed sparse column (CSC or CCS)===
| |||