Dspies

Joined 4 March 2014
7 bytes added ,  25 March 2014
Line 122: Line 122:
[[Category: Summer of Code]]
[[Category: Summer of Code]]


* Codebase Consolidation
== Codebase Consolidation ==
This is a list of things which I think need to be consolidated and cleaned up in the Octave codebase.  Before embarking on my project, I'd feel obliged to handle each of these.
This is a list of things which I think need to be consolidated and cleaned up in the Octave codebase.  Before embarking on my project, I'd feel obliged to handle each of these.
** Permutation Matrices are not index vectors.  They shouldn't subclass Array<octave_idx_type>.  They should instead contain a private instance of Array<octave_idx_type>.  Right now element_type and xelem are both wrong, and elem, checkelem, operator() all return octave_idx_type when they should return bool (for logical correctness) or double (for Matlab compatibility)
* Permutation Matrices are not index vectors.  They shouldn't subclass Array<octave_idx_type>.  They should instead contain a private instance of Array<octave_idx_type>.  Right now element_type and xelem are both wrong, and elem, checkelem, operator() all return octave_idx_type when they should return bool (for logical correctness) or double (for Matlab compatibility)
** Diagonal matrices, permutation matrices and compressed column sparse matrices are all different types of sparse matrices.  There needs to be an AbstractSparse class which is the base of DiagMatrix, PermMatrix and Sparse.  In particular, all three types should have an nz_iter which iterates over its non-zero elements in column-major order.
* Diagonal matrices, permutation matrices and compressed column sparse matrices are all different types of sparse matrices.  There needs to be an AbstractSparse class which is the base of DiagMatrix, PermMatrix and Sparse.  In particular, all three types should have an nz_iter which iterates over its non-zero elements in column-major order.
** Permuation Matrices should always be column-major.  Every other matrix type in the entire code-base is.  This bool _colp just adds unnecessary complication without granting any measurable performance boost except in extremely contrived situations.
* Permuation Matrices should always be column-major.  Every other matrix type in the entire code-base is.  This bool _colp just adds unnecessary complication without granting any measurable performance boost except in extremely contrived situations.
** The cumulative forms of max, min, all, any, sum, and product (and there should also probably be some sort of cum_xor) should all call the same function internally.  They all are forms of reduce with a different binary operation.  Right now, the implementations miss a lot of cases.  Ex try:<br />
* <p> The cumulative forms of max, min, all, any, sum, and product (and there should also probably be some sort of cum_xor) should all call the same function internally.  They all are forms of reduce with a different binary operation.  Right now, the implementations miss a lot of cases.  Ex try:<br />
max(sprand(1000000000, 20, 0.000001), [], 2);<br />
max(sprand(1000000000, 20, 0.000001), [], 2);<br />
This fails with an OOM because it wasn't considered when writing max <br />
This fails with an OOM because it wasn't considered when writing max <br />
This sort of aggregate function (over the rows) can be done in O(min(h+nnz, nnz*log(w))) time, but one would have to implement the algorithm for each of the above-mentioned 7 functions.  By consolidating these into one templated function, it'll make it worth the effort to implement.
This sort of aggregate function (over the rows) can be done in O(min(h+nnz, nnz*log(w))) time, but one would have to implement the algorithm for each of the above-mentioned 7 functions.  By consolidating these into one templated function, it'll make it worth the effort to implement.</p>
** The changes I made in https://savannah.gnu.org/patch/?8417 need to be added and need to be modified to accomodate diagonal matrices as well.  The fact that the original implementer of find neglected to handle diagonal matrices should be evidence enough that the ad-hoc approach doesn't work.
* The changes I made in https://savannah.gnu.org/patch/?8417 need to be added and need to be modified to accomodate diagonal matrices as well.  The fact that the original implementer of find neglected to handle diagonal matrices should be evidence enough that the ad-hoc approach doesn't work.
14

edits