When doing a reset, we don't need to recompute the leftmost part of the RU-decomposition, i.e. the part of the matrices R and U corresponding to columns indexed before the first permuted column.
This optimization is likely to offer a significant speedup of barcode template computations.
Notes:
1)However, it will necessitate a modification of our approach to deciding whether or not to do a reset. The simplest thing would be to assume that the cost of doing a reset is proportional to the number of columns we are reducing. A more sophisticated approach could involve collecting timing data for the resets as a function of the index of the first permutation.
2)I do not know how to do an analogous optimization to avoid recomputing the parts of the matrices R and U corresponding to columns indexed after the last permuted column. Roy looked at this a year ago, and we had some detailed discussion of this. I don't remember the specifics well, but I was left with the impression that any effort to try to use information from the right side of the matrices in the reset was not worth the trouble. However, it could well be that there is a nice way to make this work that we missed.
When doing a reset, we don't need to recompute the leftmost part of the RU-decomposition, i.e. the part of the matrices R and U corresponding to columns indexed before the first permuted column.
This optimization is likely to offer a significant speedup of barcode template computations.
Notes: 1)However, it will necessitate a modification of our approach to deciding whether or not to do a reset. The simplest thing would be to assume that the cost of doing a reset is proportional to the number of columns we are reducing. A more sophisticated approach could involve collecting timing data for the resets as a function of the index of the first permutation.
2)I do not know how to do an analogous optimization to avoid recomputing the parts of the matrices R and U corresponding to columns indexed after the last permuted column. Roy looked at this a year ago, and we had some detailed discussion of this. I don't remember the specifics well, but I was left with the impression that any effort to try to use information from the right side of the matrices in the reset was not worth the trouble. However, it could well be that there is a nice way to make this work that we missed.