You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@systemds.apache.org by GitBox <gi...@apache.org> on 2022/06/09 23:18:13 UTC
[GitHub] [systemds] wedenigt opened a new pull request, #1634: [SYSTEMDS-2830] Functional Compression
wedenigt opened a new pull request, #1634:
URL: https://github.com/apache/systemds/pull/1634
This commit introduces a new column group called `ColGroupLinearFunctional`. The column group represents each column as a linear function (i.e., intercept & slope). Each linear function is computed such that it minimizes the quadratic distance to the data points in the respective column.
`ColGroupLinearFunctional` implements
- Efficient transposed self matrix multiplication `tsmm` (which runs in `O(numCols^2)`)
- Multiplication with other `ColGroups` (which is especially efficient if another transposed `ColGroupLinearFunctional` is multiplied from the left) and with `MatrixBlock` (from the right)
- `max`, `min`, `sum`, `sumSq`, `colProduct`, `colSums`, `colSumsSq`, `rowProduct`, `rowSums`, `decompressToDenseBlock`, `decompressToSparseBlock`
The implementations of `ColGroupLinearFunctional` and of the line-fitting module `LinearRegression` are accompanied by test cases.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@systemds.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [systemds] Baunsgaard commented on a diff in pull request #1634: [SYSTEMDS-2830] Functional Compression
Posted by GitBox <gi...@apache.org>.
Baunsgaard commented on code in PR #1634:
URL: https://github.com/apache/systemds/pull/1634#discussion_r894466492
##########
src/test/java/org/apache/sysds/test/component/compress/colgroup/ColGroupLinearFunctionalTest.java:
##########
@@ -0,0 +1,547 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.sysds.test.component.compress.colgroup;
+
+import org.apache.commons.logging.Log;
+import org.apache.commons.logging.LogFactory;
+import org.apache.sysds.runtime.DMLRuntimeException;
+import org.apache.sysds.runtime.compress.CompressionSettings;
+import org.apache.sysds.runtime.compress.CompressionSettingsBuilder;
+import org.apache.sysds.runtime.compress.colgroup.AColGroup;
+import org.apache.sysds.runtime.compress.colgroup.ColGroupFactory;
+import org.apache.sysds.runtime.compress.colgroup.ColGroupUncompressed;
+import org.apache.sysds.runtime.compress.estim.CompressedSizeEstimatorExact;
+import org.apache.sysds.runtime.compress.estim.CompressedSizeInfo;
+import org.apache.sysds.runtime.compress.estim.CompressedSizeInfoColGroup;
+import org.apache.sysds.runtime.controlprogram.parfor.stat.InfrastructureAnalyzer;
+import org.apache.sysds.runtime.functionobjects.*;
+import org.apache.sysds.runtime.matrix.data.LibMatrixMult;
+import org.apache.sysds.runtime.matrix.data.LibMatrixReorg;
+import org.apache.sysds.runtime.matrix.data.MatrixBlock;
+import org.apache.sysds.runtime.matrix.operators.AggregateOperator;
+import org.apache.sysds.runtime.matrix.operators.AggregateUnaryOperator;
+import org.apache.sysds.runtime.util.DataConverter;
+import org.junit.Assert;
+import org.junit.Test;
+
+import java.util.EnumSet;
+import java.util.Random;
+
+public class ColGroupLinearFunctionalTest {
Review Comment:
if you detect that your line suddenly is a constant or zero, i suggest you make the constructor return a ColGroupConst or ColGroupZero
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@systemds.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [systemds] Baunsgaard commented on a diff in pull request #1634: [SYSTEMDS-2830] Functional Compression
Posted by GitBox <gi...@apache.org>.
Baunsgaard commented on code in PR #1634:
URL: https://github.com/apache/systemds/pull/1634#discussion_r894466492
##########
src/test/java/org/apache/sysds/test/component/compress/colgroup/ColGroupLinearFunctionalTest.java:
##########
@@ -0,0 +1,547 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.sysds.test.component.compress.colgroup;
+
+import org.apache.commons.logging.Log;
+import org.apache.commons.logging.LogFactory;
+import org.apache.sysds.runtime.DMLRuntimeException;
+import org.apache.sysds.runtime.compress.CompressionSettings;
+import org.apache.sysds.runtime.compress.CompressionSettingsBuilder;
+import org.apache.sysds.runtime.compress.colgroup.AColGroup;
+import org.apache.sysds.runtime.compress.colgroup.ColGroupFactory;
+import org.apache.sysds.runtime.compress.colgroup.ColGroupUncompressed;
+import org.apache.sysds.runtime.compress.estim.CompressedSizeEstimatorExact;
+import org.apache.sysds.runtime.compress.estim.CompressedSizeInfo;
+import org.apache.sysds.runtime.compress.estim.CompressedSizeInfoColGroup;
+import org.apache.sysds.runtime.controlprogram.parfor.stat.InfrastructureAnalyzer;
+import org.apache.sysds.runtime.functionobjects.*;
+import org.apache.sysds.runtime.matrix.data.LibMatrixMult;
+import org.apache.sysds.runtime.matrix.data.LibMatrixReorg;
+import org.apache.sysds.runtime.matrix.data.MatrixBlock;
+import org.apache.sysds.runtime.matrix.operators.AggregateOperator;
+import org.apache.sysds.runtime.matrix.operators.AggregateUnaryOperator;
+import org.apache.sysds.runtime.util.DataConverter;
+import org.junit.Assert;
+import org.junit.Test;
+
+import java.util.EnumSet;
+import java.util.Random;
+
+public class ColGroupLinearFunctionalTest {
Review Comment:
if you detect that your line suddenly is a constant or zero, i suggest you make the constructor return a ColGroupConst or ColGroupZero.
Do this behind a create method, and make the constructor for the column group private.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@systemds.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [systemds] wedenigt commented on a diff in pull request #1634: [SYSTEMDS-2830] Functional Compression
Posted by GitBox <gi...@apache.org>.
wedenigt commented on code in PR #1634:
URL: https://github.com/apache/systemds/pull/1634#discussion_r902390408
##########
src/test/java/org/apache/sysds/test/component/compress/colgroup/ColGroupLinearFunctionalTest.java:
##########
@@ -0,0 +1,547 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.sysds.test.component.compress.colgroup;
+
+import org.apache.commons.logging.Log;
+import org.apache.commons.logging.LogFactory;
+import org.apache.sysds.runtime.DMLRuntimeException;
+import org.apache.sysds.runtime.compress.CompressionSettings;
+import org.apache.sysds.runtime.compress.CompressionSettingsBuilder;
+import org.apache.sysds.runtime.compress.colgroup.AColGroup;
+import org.apache.sysds.runtime.compress.colgroup.ColGroupFactory;
+import org.apache.sysds.runtime.compress.colgroup.ColGroupUncompressed;
+import org.apache.sysds.runtime.compress.estim.CompressedSizeEstimatorExact;
+import org.apache.sysds.runtime.compress.estim.CompressedSizeInfo;
+import org.apache.sysds.runtime.compress.estim.CompressedSizeInfoColGroup;
+import org.apache.sysds.runtime.controlprogram.parfor.stat.InfrastructureAnalyzer;
+import org.apache.sysds.runtime.functionobjects.*;
+import org.apache.sysds.runtime.matrix.data.LibMatrixMult;
+import org.apache.sysds.runtime.matrix.data.LibMatrixReorg;
+import org.apache.sysds.runtime.matrix.data.MatrixBlock;
+import org.apache.sysds.runtime.matrix.operators.AggregateOperator;
+import org.apache.sysds.runtime.matrix.operators.AggregateUnaryOperator;
+import org.apache.sysds.runtime.util.DataConverter;
+import org.junit.Assert;
+import org.junit.Test;
+
+import java.util.EnumSet;
+import java.util.Random;
+
+public class ColGroupLinearFunctionalTest {
Review Comment:
> if you detect that your line suddenly is a constant or zero, i suggest you make the constructor return a ColGroupConst or ColGroupZero. Do this behind a create method, and make the constructor for the column group private.
I have added this feature, however, it seems that the `ColGroupFactory` already does these checks (it checks `getBestCompressionType`) and thus, the `create` method of `ColGroupLinearFunctional` is never called.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@systemds.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [systemds] Baunsgaard closed pull request #1634: [SYSTEMDS-2830] Functional Compression
Posted by GitBox <gi...@apache.org>.
Baunsgaard closed pull request #1634: [SYSTEMDS-2830] Functional Compression
URL: https://github.com/apache/systemds/pull/1634
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@systemds.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [systemds] Baunsgaard commented on a diff in pull request #1634: [SYSTEMDS-2830] Functional Compression
Posted by GitBox <gi...@apache.org>.
Baunsgaard commented on code in PR #1634:
URL: https://github.com/apache/systemds/pull/1634#discussion_r905109205
##########
src/test/java/org/apache/sysds/test/component/compress/colgroup/ColGroupLinearFunctionalTest.java:
##########
@@ -0,0 +1,547 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.sysds.test.component.compress.colgroup;
+
+import org.apache.commons.logging.Log;
+import org.apache.commons.logging.LogFactory;
+import org.apache.sysds.runtime.DMLRuntimeException;
+import org.apache.sysds.runtime.compress.CompressionSettings;
+import org.apache.sysds.runtime.compress.CompressionSettingsBuilder;
+import org.apache.sysds.runtime.compress.colgroup.AColGroup;
+import org.apache.sysds.runtime.compress.colgroup.ColGroupFactory;
+import org.apache.sysds.runtime.compress.colgroup.ColGroupUncompressed;
+import org.apache.sysds.runtime.compress.estim.CompressedSizeEstimatorExact;
+import org.apache.sysds.runtime.compress.estim.CompressedSizeInfo;
+import org.apache.sysds.runtime.compress.estim.CompressedSizeInfoColGroup;
+import org.apache.sysds.runtime.controlprogram.parfor.stat.InfrastructureAnalyzer;
+import org.apache.sysds.runtime.functionobjects.*;
+import org.apache.sysds.runtime.matrix.data.LibMatrixMult;
+import org.apache.sysds.runtime.matrix.data.LibMatrixReorg;
+import org.apache.sysds.runtime.matrix.data.MatrixBlock;
+import org.apache.sysds.runtime.matrix.operators.AggregateOperator;
+import org.apache.sysds.runtime.matrix.operators.AggregateUnaryOperator;
+import org.apache.sysds.runtime.util.DataConverter;
+import org.junit.Assert;
+import org.junit.Test;
+
+import java.util.EnumSet;
+import java.util.Random;
+
+public class ColGroupLinearFunctionalTest {
Review Comment:
yes, it does the checks when constructing a new column group from uncompressed input, the checks are mainly for when you perform operations on the functional compression, and for some reason it ends up as a constant or zero. This makes you construct a functional group rather than the much cheaper const or empty groups if naively implemented.
Hence making a constructor that is able to return these other types is beneficial.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@systemds.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [systemds] wedenigt commented on a diff in pull request #1634: [SYSTEMDS-2830] Functional Compression
Posted by GitBox <gi...@apache.org>.
wedenigt commented on code in PR #1634:
URL: https://github.com/apache/systemds/pull/1634#discussion_r905185230
##########
src/test/java/org/apache/sysds/test/component/compress/colgroup/ColGroupLinearFunctionalTest.java:
##########
@@ -0,0 +1,547 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.sysds.test.component.compress.colgroup;
+
+import org.apache.commons.logging.Log;
+import org.apache.commons.logging.LogFactory;
+import org.apache.sysds.runtime.DMLRuntimeException;
+import org.apache.sysds.runtime.compress.CompressionSettings;
+import org.apache.sysds.runtime.compress.CompressionSettingsBuilder;
+import org.apache.sysds.runtime.compress.colgroup.AColGroup;
+import org.apache.sysds.runtime.compress.colgroup.ColGroupFactory;
+import org.apache.sysds.runtime.compress.colgroup.ColGroupUncompressed;
+import org.apache.sysds.runtime.compress.estim.CompressedSizeEstimatorExact;
+import org.apache.sysds.runtime.compress.estim.CompressedSizeInfo;
+import org.apache.sysds.runtime.compress.estim.CompressedSizeInfoColGroup;
+import org.apache.sysds.runtime.controlprogram.parfor.stat.InfrastructureAnalyzer;
+import org.apache.sysds.runtime.functionobjects.*;
+import org.apache.sysds.runtime.matrix.data.LibMatrixMult;
+import org.apache.sysds.runtime.matrix.data.LibMatrixReorg;
+import org.apache.sysds.runtime.matrix.data.MatrixBlock;
+import org.apache.sysds.runtime.matrix.operators.AggregateOperator;
+import org.apache.sysds.runtime.matrix.operators.AggregateUnaryOperator;
+import org.apache.sysds.runtime.util.DataConverter;
+import org.junit.Assert;
+import org.junit.Test;
+
+import java.util.EnumSet;
+import java.util.Random;
+
+public class ColGroupLinearFunctionalTest {
Review Comment:
Alright, got it. Thanks for the explanation.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@systemds.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [systemds] Baunsgaard commented on a diff in pull request #1634: [SYSTEMDS-2830] Functional Compression
Posted by GitBox <gi...@apache.org>.
Baunsgaard commented on code in PR #1634:
URL: https://github.com/apache/systemds/pull/1634#discussion_r894423763
##########
src/main/java/org/apache/sysds/runtime/compress/colgroup/functional/LinearRegression.java:
##########
@@ -0,0 +1,57 @@
+package org.apache.sysds.runtime.compress.colgroup.functional;
Review Comment:
Missing license
##########
src/main/java/org/apache/sysds/runtime/compress/colgroup/functional/LinearRegression.java:
##########
@@ -0,0 +1,57 @@
+package org.apache.sysds.runtime.compress.colgroup.functional;
+
+import org.apache.sysds.runtime.compress.DMLCompressionException;
+import org.apache.sysds.runtime.compress.readers.ReaderColumnSelection;
+import org.apache.sysds.runtime.compress.utils.DblArray;
+import org.apache.sysds.runtime.matrix.data.MatrixBlock;
+
+public class LinearRegression {
+ public static double[][] regressMatrixBlock(MatrixBlock rawBlock, int[] colIndexes, boolean transposed) {
+ final int nRows = transposed ? rawBlock.getNumColumns() : rawBlock.getNumRows();
+
+ if(nRows <= 1) {
+ throw new DMLCompressionException("At least 2 data points are required to fit a linear function.");
+ }
Review Comment:
since it is a one liner i remove brackets
##########
src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupLinearFunctional.java:
##########
@@ -0,0 +1,516 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.sysds.runtime.compress.colgroup;
+
+import org.apache.commons.lang.NotImplementedException;
+import org.apache.sysds.runtime.compress.DMLCompressionException;
+import org.apache.sysds.runtime.compress.cost.ComputationCostEstimator;
+import org.apache.sysds.runtime.compress.utils.Util;
+import org.apache.sysds.runtime.controlprogram.parfor.stat.InfrastructureAnalyzer;
+import org.apache.sysds.runtime.data.DenseBlock;
+import org.apache.sysds.runtime.data.SparseBlock;
+import org.apache.sysds.runtime.functionobjects.Builtin;
+import org.apache.sysds.runtime.instructions.cp.CM_COV_Object;
+import org.apache.sysds.runtime.matrix.data.LibMatrixMult;
+import org.apache.sysds.runtime.matrix.data.LibMatrixReorg;
+import org.apache.sysds.runtime.matrix.data.MatrixBlock;
+import org.apache.sysds.runtime.matrix.operators.BinaryOperator;
+import org.apache.sysds.runtime.matrix.operators.CMOperator;
+import org.apache.sysds.runtime.matrix.operators.ScalarOperator;
+import org.apache.sysds.runtime.matrix.operators.UnaryOperator;
+import org.apache.sysds.runtime.util.DataConverter;
+
+import java.io.DataInput;
+import java.io.DataOutput;
+import java.io.IOException;
+import java.util.Arrays;
+
+public class ColGroupLinearFunctional extends AColGroupCompressed {
+
+ private static final long serialVersionUID = -2811822570758221975L;
+
+ protected double[][] _coefficents;
+
+ protected int _numRows;
+
+ /** Constructor for serialization */
+ protected ColGroupLinearFunctional() {
+ super();
+ }
+
+ /**
+ * Constructs a Linear Functional Column Group that compresses its content using a linear functional.
+ *
+ * @param colIndices The Column indexes for the column group.
+ * @param coefficents 2D-Array where coefficients[0] is the list of intercepts and coefficients[1] the list of slopes.
+ * @param numRows Number of rows encoded within this column group.
+ */
+ private ColGroupLinearFunctional(int[] colIndices, double[][] coefficents, int numRows) {
+ super(colIndices);
+ this._coefficents = coefficents;
+ this._numRows = numRows;
+ }
+
+ /**
+ * Generate a linear functional column group.
+ *
+ * @param colIndices The specific column indexes that is contained in this column group.
+ * @param coefficents 2D-Array where coefficients[0] is the list of intercepts and coefficients[1] the list of slopes.
+ * @param numRows Number of rows encoded within this column group.
+ * @return A LinearFunctional column group.
+ */
+ public static AColGroup create(int[] colIndices, double[][] coefficents, int numRows) {
+ if(coefficents.length != 2 || colIndices.length != coefficents[0].length)
+ throw new DMLCompressionException("Invalid size of values compared to columns");
+ return new ColGroupLinearFunctional(colIndices, coefficents, numRows);
+ }
+
+
+ @Override
+ protected void computeRowMxx(double[] c, Builtin builtin, int rl, int ru, double[] preAgg) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public CompressionType getCompType() {
+ return CompressionType.LinearFunctional;
+ }
+
+ @Override
+ public ColGroupType getColGroupType() {
+ return ColGroupType.LinearFunctional;
+ }
+
+ @Override
+ public double getMin() {
+ double min = Double.POSITIVE_INFINITY;
+
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ if(slope >= 0 && (intercept + slope) < min) {
+ min = intercept + slope;
+ }
+ else if(slope < 0 && (intercept + _numRows * slope) < min) {
+ min = intercept + _numRows * slope;
+ }
+ }
+
+ return min;
+ }
+
+ @Override
+ public double getMax() {
+ double max = Double.NEGATIVE_INFINITY;
+
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ if(slope >= 0 && (intercept + _numRows * slope) > max) {
+ max = intercept + _numRows * slope;
+ }
+ else if(slope < 0 && (intercept + slope) > max) {
+ max = intercept + slope;
+ }
+ }
+
+ return max;
+ }
+
+ @Override
+ public void decompressToDenseBlock(DenseBlock db, int rl, int ru, int offR, int offC) {
+ int offT = rl + offR;
+ final int nCol = _colIndexes.length;
+ int offS = rl * nCol;
+ for(int row = rl; row < ru; row++, offT++, offS += nCol) {
+ final double[] c = db.values(offT);
+ final int off = db.pos(offT) + offC;
+ for(int j = 0; j < nCol; j++)
+ c[off + _colIndexes[j]] += getIdx(row, j);
Review Comment:
ideally you would design this decompress in a way to not call getIdx.
I think perhaps you could consider allocating a small double[] vector that you then modify for each row with the slope value.
##########
src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupSizes.java:
##########
@@ -107,4 +107,14 @@ public static long estimateInMemorySizeUncompressed(int nrRows, int nrColumns, d
size += MatrixBlock.estimateSizeInMemory(nrRows, nrColumns, (nrColumns > 1) ? sparsity : 1);
return size;
}
+
+ public static long estimateInMemorySizeLinearFunctional(int nrColumns) {
+ long size = 0;
+ // Since the Object is a col group the overhead from the Memory Size group is added
+ size += estimateInMemorySizeGroup(nrColumns);
+ size += 2L * 8L * nrColumns; // coefficients; per column, we store 2 doubles (slope & intercept)
Review Comment:
This is wrong.
The size of a double[][] array is first the size of the outer object pointer array
use: https://github.com/apache/systemds/blob/8d0195a666d3871582b9691c2b97a65cee387780/src/main/java/org/apache/sysds/utils/MemoryEstimates.java#L139
then each inner array of double[]
use: https://github.com/apache/systemds/blob/8d0195a666d3871582b9691c2b97a65cee387780/src/main/java/org/apache/sysds/utils/MemoryEstimates.java#L124
Ideally i would suggest that you allocate a dense double[] to avoid the extra level of [][].
##########
src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupLinearFunctional.java:
##########
@@ -0,0 +1,516 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.sysds.runtime.compress.colgroup;
+
+import org.apache.commons.lang.NotImplementedException;
+import org.apache.sysds.runtime.compress.DMLCompressionException;
+import org.apache.sysds.runtime.compress.cost.ComputationCostEstimator;
+import org.apache.sysds.runtime.compress.utils.Util;
+import org.apache.sysds.runtime.controlprogram.parfor.stat.InfrastructureAnalyzer;
+import org.apache.sysds.runtime.data.DenseBlock;
+import org.apache.sysds.runtime.data.SparseBlock;
+import org.apache.sysds.runtime.functionobjects.Builtin;
+import org.apache.sysds.runtime.instructions.cp.CM_COV_Object;
+import org.apache.sysds.runtime.matrix.data.LibMatrixMult;
+import org.apache.sysds.runtime.matrix.data.LibMatrixReorg;
+import org.apache.sysds.runtime.matrix.data.MatrixBlock;
+import org.apache.sysds.runtime.matrix.operators.BinaryOperator;
+import org.apache.sysds.runtime.matrix.operators.CMOperator;
+import org.apache.sysds.runtime.matrix.operators.ScalarOperator;
+import org.apache.sysds.runtime.matrix.operators.UnaryOperator;
+import org.apache.sysds.runtime.util.DataConverter;
+
+import java.io.DataInput;
+import java.io.DataOutput;
+import java.io.IOException;
+import java.util.Arrays;
+
+public class ColGroupLinearFunctional extends AColGroupCompressed {
+
+ private static final long serialVersionUID = -2811822570758221975L;
+
+ protected double[][] _coefficents;
+
+ protected int _numRows;
+
+ /** Constructor for serialization */
+ protected ColGroupLinearFunctional() {
+ super();
+ }
+
+ /**
+ * Constructs a Linear Functional Column Group that compresses its content using a linear functional.
+ *
+ * @param colIndices The Column indexes for the column group.
+ * @param coefficents 2D-Array where coefficients[0] is the list of intercepts and coefficients[1] the list of slopes.
+ * @param numRows Number of rows encoded within this column group.
+ */
+ private ColGroupLinearFunctional(int[] colIndices, double[][] coefficents, int numRows) {
+ super(colIndices);
+ this._coefficents = coefficents;
+ this._numRows = numRows;
+ }
+
+ /**
+ * Generate a linear functional column group.
+ *
+ * @param colIndices The specific column indexes that is contained in this column group.
+ * @param coefficents 2D-Array where coefficients[0] is the list of intercepts and coefficients[1] the list of slopes.
+ * @param numRows Number of rows encoded within this column group.
+ * @return A LinearFunctional column group.
+ */
+ public static AColGroup create(int[] colIndices, double[][] coefficents, int numRows) {
+ if(coefficents.length != 2 || colIndices.length != coefficents[0].length)
+ throw new DMLCompressionException("Invalid size of values compared to columns");
+ return new ColGroupLinearFunctional(colIndices, coefficents, numRows);
+ }
+
+
+ @Override
+ protected void computeRowMxx(double[] c, Builtin builtin, int rl, int ru, double[] preAgg) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public CompressionType getCompType() {
+ return CompressionType.LinearFunctional;
+ }
+
+ @Override
+ public ColGroupType getColGroupType() {
+ return ColGroupType.LinearFunctional;
+ }
+
+ @Override
+ public double getMin() {
+ double min = Double.POSITIVE_INFINITY;
+
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ if(slope >= 0 && (intercept + slope) < min) {
+ min = intercept + slope;
+ }
+ else if(slope < 0 && (intercept + _numRows * slope) < min) {
+ min = intercept + _numRows * slope;
+ }
+ }
+
+ return min;
+ }
+
+ @Override
+ public double getMax() {
+ double max = Double.NEGATIVE_INFINITY;
+
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ if(slope >= 0 && (intercept + _numRows * slope) > max) {
+ max = intercept + _numRows * slope;
+ }
+ else if(slope < 0 && (intercept + slope) > max) {
+ max = intercept + slope;
+ }
+ }
+
+ return max;
+ }
+
+ @Override
+ public void decompressToDenseBlock(DenseBlock db, int rl, int ru, int offR, int offC) {
+ int offT = rl + offR;
+ final int nCol = _colIndexes.length;
+ int offS = rl * nCol;
+ for(int row = rl; row < ru; row++, offT++, offS += nCol) {
+ final double[] c = db.values(offT);
+ final int off = db.pos(offT) + offC;
+ for(int j = 0; j < nCol; j++)
+ c[off + _colIndexes[j]] += getIdx(row, j);
+ }
+ }
+
+ @Override
+ public void decompressToSparseBlock(SparseBlock ret, int rl, int ru, int offR, int offC) {
+ final int nCol = _colIndexes.length;
+ for(int i = rl, offT = rl + offR; i < ru; i++, offT++) {
+ for(int j = 0; j < nCol; j++)
+ ret.append(offT, _colIndexes[j] + offC, getIdx(i, j));
+ }
+ }
+
+ @Override
+ public double getIdx(int r, int colIdx) {
+ return _coefficents[0][colIdx] + _coefficents[1][colIdx] * (r + 1);
+ }
+
+ @Override
+ public AColGroup scalarOperation(ScalarOperator op) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup unaryOperation(UnaryOperator op) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup binaryRowOpLeft(BinaryOperator op, double[] v, boolean isRowSafe) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup binaryRowOpRight(BinaryOperator op, double[] v, boolean isRowSafe) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected double computeMxx(double c, Builtin builtin) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected void computeColMxx(double[] c, Builtin builtin) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected void computeSum(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[0] += nRows * (intercept + (nRows + 1) * slope / 2);
+ }
+ }
+
+ @Override
+ public void computeColSums(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[_colIndexes[col]] += nRows * (intercept + (nRows + 1) * slope / 2);
+ }
+ }
+
+ @Override
+ protected void computeSumSq(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[0] += nRows * (Math.pow(intercept, 2) + (nRows + 1) * slope * intercept +
+ (nRows + 1) * (2 * nRows + 1) * Math.pow(slope, 2) / 6);
+ }
+ }
+
+ @Override
+ protected void computeColSumsSq(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[_colIndexes[col]] += nRows * (Math.pow(intercept, 2) + (nRows + 1) * slope * intercept +
+ (nRows + 1) * (2 * nRows + 1) * Math.pow(slope, 2) / 6);
+ }
+ }
+
+ @Override
+ protected void computeRowSums(double[] c, int rl, int ru, double[] preAgg) {
+ double intercept_sum = 0;
+ for(double intercept : _coefficents[0])
+ intercept_sum += intercept;
+
+ double slope_sum = 0;
+ for(double slope : _coefficents[1])
+ slope_sum += slope;
+
+ for(int rix = rl; rix < ru; rix++)
+ c[rix] += intercept_sum + slope_sum * (rix + 1);
+ }
+
+ @Override
+ public int getNumValues() {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup rightMultByMatrix(MatrixBlock right) {
+ final int nColR = right.getNumColumns();
+ final int[] outputCols = Util.genColsIndices(nColR);
+
+ MatrixBlock result = new MatrixBlock(_numRows, nColR, false);
+ for(int j = 0; j < nColR; j++) {
+ double bias_accum = 0.0;
+ double slope_accum = 0.0;
+
+ for(int c = 0; c < _colIndexes.length; c++) {
+ bias_accum += right.getValue(_colIndexes[c], j) * _coefficents[0][c];
+ slope_accum += right.getValue(_colIndexes[c], j) * _coefficents[1][c];
+ }
+
+ for(int r = 0; r < _numRows; r++) {
+ result.setValue(r, j, bias_accum + (r+1) * slope_accum);
+ }
+ }
+
+ // returns an uncompressed ColGroup
+ return ColGroupUncompressed.create(result, outputCols);
+ }
+
+ @Override
+ public void tsmm(double[] ret, int numColumns, int nRows) {
+ // runs in O(tCol^2) since dot-products take O(1) time to compute when both vectors are linearly compressed
+ final int tCol = _colIndexes.length;
+
+ final double sumIndices = nRows * (nRows + 1)/2.0;
+ final double sumSquaredIndices = nRows * (nRows + 1) * (2*nRows + 1)/6.0;
+ for(int row = 0, offTmp = 0; row < tCol; row++, offTmp += tCol) {
+ final double alpha1 = nRows * _coefficents[0][row] + sumIndices * _coefficents[1][row];
+ final double alpha2 = sumIndices * _coefficents[0][row] + sumSquaredIndices * _coefficents[1][row];
+ final int offRet = _colIndexes[row] * numColumns;
+ for(int col = row; col < tCol; col++) {
+ ret[offRet + _colIndexes[col]] += alpha1 * _coefficents[0][col] + alpha2 * _coefficents[1][col];
+ }
+ }
+ }
+
+ @Override
+ public void leftMultByMatrixNoPreAgg(MatrixBlock matrix, MatrixBlock result, int rl, int ru, int cl, int cu) {
+ throw new DMLCompressionException("This method should never be called");
+ }
+
+ @Override
+ public void leftMultByAColGroup(AColGroup lhs, MatrixBlock result) {
+ if(lhs instanceof ColGroupEmpty) {
+ return;
+ }
+
+ MatrixBlock tmpRet = new MatrixBlock(lhs.getNumCols(), _colIndexes.length, 0);
+
+ if(lhs instanceof ColGroupUncompressed) {
+ ColGroupUncompressed lhsUC = (ColGroupUncompressed) lhs;
+ int numRowsLeft = lhsUC.getData().getNumRows();
+
+ double[] colSumsAndWeightedColSums = new double[2 * lhs.getNumCols()];
+ for(int j = 0, offTmp = 0; j < lhs.getNumCols(); j++, offTmp += 2) {
+ for(int i = 0; i < numRowsLeft; i++) {
+ colSumsAndWeightedColSums[offTmp] += lhs.getIdx(i, j);
+ colSumsAndWeightedColSums[offTmp + 1] += (i+1) * lhs.getIdx(i, j);
+ }
+ }
+
+ MatrixBlock sumMatrix = new MatrixBlock(lhs.getNumCols(), 2, colSumsAndWeightedColSums);
+ MatrixBlock coefficientMatrix = DataConverter.convertToMatrixBlock(_coefficents);
+
+ LibMatrixMult.matrixMult(sumMatrix, coefficientMatrix, tmpRet);
+ } else if(lhs instanceof ColGroupLinearFunctional) {
+ ColGroupLinearFunctional lhsLF = (ColGroupLinearFunctional) lhs;
+
+ final double sumIndices = _numRows * (_numRows + 1)/2.0;
+ final double sumSquaredIndices = _numRows * (_numRows + 1) * (2*_numRows + 1)/6.0;
+
+ MatrixBlock weightMatrix = new MatrixBlock(2, 2, new double[] {_numRows, sumIndices, sumIndices, sumSquaredIndices});
+ MatrixBlock coefficientMatrixLhs = DataConverter.convertToMatrixBlock(lhsLF._coefficents);
+ MatrixBlock coefficientMatrixRhs = DataConverter.convertToMatrixBlock(_coefficents);
+
+ coefficientMatrixLhs = LibMatrixReorg.transposeInPlace(coefficientMatrixLhs,
+ InfrastructureAnalyzer.getLocalParallelism());
+
+ // We simply compute a matrix multiplication chain in coefficient space, i.e.,
+ // t(L) %*% R = t(coeff(L)) %*% W %*% coeff(R)
+ // where W is a weight matrix capturing the size of the shared dimension (weightMatrix above)
+ // and coeff(X) denotes the 2 x n matrix of the m x n matrix X.
+ MatrixBlock tmp = new MatrixBlock(lhs.getNumCols(), 2, false);
+ LibMatrixMult.matrixMult(coefficientMatrixLhs, weightMatrix, tmp);
+ LibMatrixMult.matrixMult(tmp, coefficientMatrixRhs, tmpRet);
+ } else if(lhs instanceof APreAgg) {
+ // TODO: implement
+ throw new NotImplementedException();
+ } else {
+ throw new NotImplementedException();
+ }
+
+ final double[] resV = result.getDenseBlockValues();
+ if(tmpRet.isEmpty())
+ return;
+ else if(tmpRet.isInSparseFormat()) {
+ SparseBlock sb = tmpRet.getSparseBlock();
+ for(int row = 0; row < lhs._colIndexes.length; row++) {
+ if(sb.isEmpty(row))
+ continue;
+ final int apos = sb.pos(row);
+ final int alen = sb.size(row) + apos;
+ final int[] aix = sb.indexes(row);
+ final double[] avals = sb.values(row);
+ final int offRes = lhs._colIndexes[row] * result.getNumColumns();
+ for(int col = apos; col < alen; col++)
+ resV[offRes + _colIndexes[aix[col]]] += avals[col];
+ }
+ }
+ else {
+ double[] tmpRetV = tmpRet.getDenseBlockValues();
+ for(int row = 0; row < lhs.getNumCols(); row++) {
+ final int offRes = lhs._colIndexes[row] * result.getNumColumns();
+ final int offTmp = row * getNumCols();
+ for(int col = 0; col < getNumCols(); col++) {
+ resV[offRes + _colIndexes[col]] += tmpRetV[offTmp + col];
+ }
+ }
+ }
Review Comment:
this code looks suspiciously much like the code inside ColGroupUncompressed,
i suggest that we combine the two into a util function in ColGroupUtil.
##########
src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupLinearFunctional.java:
##########
@@ -0,0 +1,516 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.sysds.runtime.compress.colgroup;
+
+import org.apache.commons.lang.NotImplementedException;
+import org.apache.sysds.runtime.compress.DMLCompressionException;
+import org.apache.sysds.runtime.compress.cost.ComputationCostEstimator;
+import org.apache.sysds.runtime.compress.utils.Util;
+import org.apache.sysds.runtime.controlprogram.parfor.stat.InfrastructureAnalyzer;
+import org.apache.sysds.runtime.data.DenseBlock;
+import org.apache.sysds.runtime.data.SparseBlock;
+import org.apache.sysds.runtime.functionobjects.Builtin;
+import org.apache.sysds.runtime.instructions.cp.CM_COV_Object;
+import org.apache.sysds.runtime.matrix.data.LibMatrixMult;
+import org.apache.sysds.runtime.matrix.data.LibMatrixReorg;
+import org.apache.sysds.runtime.matrix.data.MatrixBlock;
+import org.apache.sysds.runtime.matrix.operators.BinaryOperator;
+import org.apache.sysds.runtime.matrix.operators.CMOperator;
+import org.apache.sysds.runtime.matrix.operators.ScalarOperator;
+import org.apache.sysds.runtime.matrix.operators.UnaryOperator;
+import org.apache.sysds.runtime.util.DataConverter;
+
+import java.io.DataInput;
+import java.io.DataOutput;
+import java.io.IOException;
+import java.util.Arrays;
+
+public class ColGroupLinearFunctional extends AColGroupCompressed {
+
+ private static final long serialVersionUID = -2811822570758221975L;
+
+ protected double[][] _coefficents;
+
+ protected int _numRows;
+
+ /** Constructor for serialization */
+ protected ColGroupLinearFunctional() {
+ super();
+ }
+
+ /**
+ * Constructs a Linear Functional Column Group that compresses its content using a linear functional.
+ *
+ * @param colIndices The Column indexes for the column group.
+ * @param coefficents 2D-Array where coefficients[0] is the list of intercepts and coefficients[1] the list of slopes.
+ * @param numRows Number of rows encoded within this column group.
+ */
+ private ColGroupLinearFunctional(int[] colIndices, double[][] coefficents, int numRows) {
+ super(colIndices);
+ this._coefficents = coefficents;
+ this._numRows = numRows;
+ }
+
+ /**
+ * Generate a linear functional column group.
+ *
+ * @param colIndices The specific column indexes that is contained in this column group.
+ * @param coefficents 2D-Array where coefficients[0] is the list of intercepts and coefficients[1] the list of slopes.
+ * @param numRows Number of rows encoded within this column group.
+ * @return A LinearFunctional column group.
+ */
+ public static AColGroup create(int[] colIndices, double[][] coefficents, int numRows) {
+ if(coefficents.length != 2 || colIndices.length != coefficents[0].length)
+ throw new DMLCompressionException("Invalid size of values compared to columns");
+ return new ColGroupLinearFunctional(colIndices, coefficents, numRows);
+ }
+
+
+ @Override
+ protected void computeRowMxx(double[] c, Builtin builtin, int rl, int ru, double[] preAgg) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public CompressionType getCompType() {
+ return CompressionType.LinearFunctional;
+ }
+
+ @Override
+ public ColGroupType getColGroupType() {
+ return ColGroupType.LinearFunctional;
+ }
+
+ @Override
+ public double getMin() {
+ double min = Double.POSITIVE_INFINITY;
+
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ if(slope >= 0 && (intercept + slope) < min) {
+ min = intercept + slope;
+ }
+ else if(slope < 0 && (intercept + _numRows * slope) < min) {
+ min = intercept + _numRows * slope;
+ }
+ }
+
+ return min;
+ }
+
+ @Override
+ public double getMax() {
+ double max = Double.NEGATIVE_INFINITY;
+
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ if(slope >= 0 && (intercept + _numRows * slope) > max) {
+ max = intercept + _numRows * slope;
+ }
+ else if(slope < 0 && (intercept + slope) > max) {
+ max = intercept + slope;
+ }
+ }
+
+ return max;
+ }
+
+ @Override
+ public void decompressToDenseBlock(DenseBlock db, int rl, int ru, int offR, int offC) {
+ int offT = rl + offR;
+ final int nCol = _colIndexes.length;
+ int offS = rl * nCol;
+ for(int row = rl; row < ru; row++, offT++, offS += nCol) {
+ final double[] c = db.values(offT);
+ final int off = db.pos(offT) + offC;
+ for(int j = 0; j < nCol; j++)
+ c[off + _colIndexes[j]] += getIdx(row, j);
+ }
+ }
+
+ @Override
+ public void decompressToSparseBlock(SparseBlock ret, int rl, int ru, int offR, int offC) {
+ final int nCol = _colIndexes.length;
+ for(int i = rl, offT = rl + offR; i < ru; i++, offT++) {
+ for(int j = 0; j < nCol; j++)
+ ret.append(offT, _colIndexes[j] + offC, getIdx(i, j));
+ }
+ }
+
+ @Override
+ public double getIdx(int r, int colIdx) {
+ return _coefficents[0][colIdx] + _coefficents[1][colIdx] * (r + 1);
+ }
+
+ @Override
+ public AColGroup scalarOperation(ScalarOperator op) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup unaryOperation(UnaryOperator op) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup binaryRowOpLeft(BinaryOperator op, double[] v, boolean isRowSafe) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup binaryRowOpRight(BinaryOperator op, double[] v, boolean isRowSafe) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected double computeMxx(double c, Builtin builtin) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected void computeColMxx(double[] c, Builtin builtin) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected void computeSum(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[0] += nRows * (intercept + (nRows + 1) * slope / 2);
+ }
+ }
+
+ @Override
+ public void computeColSums(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[_colIndexes[col]] += nRows * (intercept + (nRows + 1) * slope / 2);
+ }
+ }
+
+ @Override
+ protected void computeSumSq(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[0] += nRows * (Math.pow(intercept, 2) + (nRows + 1) * slope * intercept +
+ (nRows + 1) * (2 * nRows + 1) * Math.pow(slope, 2) / 6);
+ }
+ }
+
+ @Override
+ protected void computeColSumsSq(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[_colIndexes[col]] += nRows * (Math.pow(intercept, 2) + (nRows + 1) * slope * intercept +
+ (nRows + 1) * (2 * nRows + 1) * Math.pow(slope, 2) / 6);
+ }
+ }
+
+ @Override
+ protected void computeRowSums(double[] c, int rl, int ru, double[] preAgg) {
+ double intercept_sum = 0;
+ for(double intercept : _coefficents[0])
+ intercept_sum += intercept;
+
+ double slope_sum = 0;
+ for(double slope : _coefficents[1])
+ slope_sum += slope;
+
+ for(int rix = rl; rix < ru; rix++)
+ c[rix] += intercept_sum + slope_sum * (rix + 1);
+ }
+
+ @Override
+ public int getNumValues() {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup rightMultByMatrix(MatrixBlock right) {
+ final int nColR = right.getNumColumns();
+ final int[] outputCols = Util.genColsIndices(nColR);
+
+ MatrixBlock result = new MatrixBlock(_numRows, nColR, false);
+ for(int j = 0; j < nColR; j++) {
+ double bias_accum = 0.0;
+ double slope_accum = 0.0;
+
+ for(int c = 0; c < _colIndexes.length; c++) {
+ bias_accum += right.getValue(_colIndexes[c], j) * _coefficents[0][c];
+ slope_accum += right.getValue(_colIndexes[c], j) * _coefficents[1][c];
+ }
+
+ for(int r = 0; r < _numRows; r++) {
+ result.setValue(r, j, bias_accum + (r+1) * slope_accum);
+ }
+ }
+
+ // returns an uncompressed ColGroup
+ return ColGroupUncompressed.create(result, outputCols);
+ }
+
+ @Override
+ public void tsmm(double[] ret, int numColumns, int nRows) {
+ // runs in O(tCol^2) since dot-products take O(1) time to compute when both vectors are linearly compressed
+ final int tCol = _colIndexes.length;
+
+ final double sumIndices = nRows * (nRows + 1)/2.0;
+ final double sumSquaredIndices = nRows * (nRows + 1) * (2*nRows + 1)/6.0;
+ for(int row = 0, offTmp = 0; row < tCol; row++, offTmp += tCol) {
+ final double alpha1 = nRows * _coefficents[0][row] + sumIndices * _coefficents[1][row];
+ final double alpha2 = sumIndices * _coefficents[0][row] + sumSquaredIndices * _coefficents[1][row];
+ final int offRet = _colIndexes[row] * numColumns;
+ for(int col = row; col < tCol; col++) {
+ ret[offRet + _colIndexes[col]] += alpha1 * _coefficents[0][col] + alpha2 * _coefficents[1][col];
+ }
+ }
+ }
+
+ @Override
+ public void leftMultByMatrixNoPreAgg(MatrixBlock matrix, MatrixBlock result, int rl, int ru, int cl, int cu) {
+ throw new DMLCompressionException("This method should never be called");
+ }
+
+ @Override
+ public void leftMultByAColGroup(AColGroup lhs, MatrixBlock result) {
+ if(lhs instanceof ColGroupEmpty) {
+ return;
+ }
+
+ MatrixBlock tmpRet = new MatrixBlock(lhs.getNumCols(), _colIndexes.length, 0);
+
+ if(lhs instanceof ColGroupUncompressed) {
+ ColGroupUncompressed lhsUC = (ColGroupUncompressed) lhs;
+ int numRowsLeft = lhsUC.getData().getNumRows();
+
+ double[] colSumsAndWeightedColSums = new double[2 * lhs.getNumCols()];
+ for(int j = 0, offTmp = 0; j < lhs.getNumCols(); j++, offTmp += 2) {
+ for(int i = 0; i < numRowsLeft; i++) {
+ colSumsAndWeightedColSums[offTmp] += lhs.getIdx(i, j);
+ colSumsAndWeightedColSums[offTmp + 1] += (i+1) * lhs.getIdx(i, j);
+ }
+ }
+
+ MatrixBlock sumMatrix = new MatrixBlock(lhs.getNumCols(), 2, colSumsAndWeightedColSums);
+ MatrixBlock coefficientMatrix = DataConverter.convertToMatrixBlock(_coefficents);
+
+ LibMatrixMult.matrixMult(sumMatrix, coefficientMatrix, tmpRet);
+ } else if(lhs instanceof ColGroupLinearFunctional) {
+ ColGroupLinearFunctional lhsLF = (ColGroupLinearFunctional) lhs;
+
+ final double sumIndices = _numRows * (_numRows + 1)/2.0;
+ final double sumSquaredIndices = _numRows * (_numRows + 1) * (2*_numRows + 1)/6.0;
+
+ MatrixBlock weightMatrix = new MatrixBlock(2, 2, new double[] {_numRows, sumIndices, sumIndices, sumSquaredIndices});
+ MatrixBlock coefficientMatrixLhs = DataConverter.convertToMatrixBlock(lhsLF._coefficents);
+ MatrixBlock coefficientMatrixRhs = DataConverter.convertToMatrixBlock(_coefficents);
+
+ coefficientMatrixLhs = LibMatrixReorg.transposeInPlace(coefficientMatrixLhs,
+ InfrastructureAnalyzer.getLocalParallelism());
+
+ // We simply compute a matrix multiplication chain in coefficient space, i.e.,
+ // t(L) %*% R = t(coeff(L)) %*% W %*% coeff(R)
+ // where W is a weight matrix capturing the size of the shared dimension (weightMatrix above)
+ // and coeff(X) denotes the 2 x n matrix of the m x n matrix X.
+ MatrixBlock tmp = new MatrixBlock(lhs.getNumCols(), 2, false);
+ LibMatrixMult.matrixMult(coefficientMatrixLhs, weightMatrix, tmp);
+ LibMatrixMult.matrixMult(tmp, coefficientMatrixRhs, tmpRet);
+ } else if(lhs instanceof APreAgg) {
+ // TODO: implement
+ throw new NotImplementedException();
+ } else {
+ throw new NotImplementedException();
+ }
+
+ final double[] resV = result.getDenseBlockValues();
+ if(tmpRet.isEmpty())
+ return;
+ else if(tmpRet.isInSparseFormat()) {
+ SparseBlock sb = tmpRet.getSparseBlock();
+ for(int row = 0; row < lhs._colIndexes.length; row++) {
+ if(sb.isEmpty(row))
+ continue;
+ final int apos = sb.pos(row);
+ final int alen = sb.size(row) + apos;
+ final int[] aix = sb.indexes(row);
+ final double[] avals = sb.values(row);
+ final int offRes = lhs._colIndexes[row] * result.getNumColumns();
+ for(int col = apos; col < alen; col++)
+ resV[offRes + _colIndexes[aix[col]]] += avals[col];
+ }
+ }
+ else {
+ double[] tmpRetV = tmpRet.getDenseBlockValues();
+ for(int row = 0; row < lhs.getNumCols(); row++) {
+ final int offRes = lhs._colIndexes[row] * result.getNumColumns();
+ final int offTmp = row * getNumCols();
+ for(int col = 0; col < getNumCols(); col++) {
+ resV[offRes + _colIndexes[col]] += tmpRetV[offTmp + col];
+ }
+ }
+ }
+ }
+
+ @Override
+ public void tsmmAColGroup(AColGroup other, MatrixBlock result) {
+ throw new DMLCompressionException("Should not be called");
+ }
+
+ @Override
+ protected AColGroup sliceSingleColumn(int idx) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected AColGroup sliceMultiColumns(int idStart, int idEnd, int[] outputCols) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup copy() {
+ throw new NotImplementedException();
Review Comment:
if you are a bit bold, simply return this.
since all your values should be treated as immutable.
##########
src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupLinearFunctional.java:
##########
@@ -0,0 +1,516 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.sysds.runtime.compress.colgroup;
+
+import org.apache.commons.lang.NotImplementedException;
+import org.apache.sysds.runtime.compress.DMLCompressionException;
+import org.apache.sysds.runtime.compress.cost.ComputationCostEstimator;
+import org.apache.sysds.runtime.compress.utils.Util;
+import org.apache.sysds.runtime.controlprogram.parfor.stat.InfrastructureAnalyzer;
+import org.apache.sysds.runtime.data.DenseBlock;
+import org.apache.sysds.runtime.data.SparseBlock;
+import org.apache.sysds.runtime.functionobjects.Builtin;
+import org.apache.sysds.runtime.instructions.cp.CM_COV_Object;
+import org.apache.sysds.runtime.matrix.data.LibMatrixMult;
+import org.apache.sysds.runtime.matrix.data.LibMatrixReorg;
+import org.apache.sysds.runtime.matrix.data.MatrixBlock;
+import org.apache.sysds.runtime.matrix.operators.BinaryOperator;
+import org.apache.sysds.runtime.matrix.operators.CMOperator;
+import org.apache.sysds.runtime.matrix.operators.ScalarOperator;
+import org.apache.sysds.runtime.matrix.operators.UnaryOperator;
+import org.apache.sysds.runtime.util.DataConverter;
+
+import java.io.DataInput;
+import java.io.DataOutput;
+import java.io.IOException;
+import java.util.Arrays;
+
+public class ColGroupLinearFunctional extends AColGroupCompressed {
+
+ private static final long serialVersionUID = -2811822570758221975L;
+
+ protected double[][] _coefficents;
+
+ protected int _numRows;
+
+ /** Constructor for serialization */
+ protected ColGroupLinearFunctional() {
+ super();
+ }
+
+ /**
+ * Constructs a Linear Functional Column Group that compresses its content using a linear functional.
+ *
+ * @param colIndices The Column indexes for the column group.
+ * @param coefficents 2D-Array where coefficients[0] is the list of intercepts and coefficients[1] the list of slopes.
+ * @param numRows Number of rows encoded within this column group.
+ */
+ private ColGroupLinearFunctional(int[] colIndices, double[][] coefficents, int numRows) {
+ super(colIndices);
+ this._coefficents = coefficents;
+ this._numRows = numRows;
+ }
+
+ /**
+ * Generate a linear functional column group.
+ *
+ * @param colIndices The specific column indexes that is contained in this column group.
+ * @param coefficents 2D-Array where coefficients[0] is the list of intercepts and coefficients[1] the list of slopes.
+ * @param numRows Number of rows encoded within this column group.
+ * @return A LinearFunctional column group.
+ */
+ public static AColGroup create(int[] colIndices, double[][] coefficents, int numRows) {
+ if(coefficents.length != 2 || colIndices.length != coefficents[0].length)
+ throw new DMLCompressionException("Invalid size of values compared to columns");
+ return new ColGroupLinearFunctional(colIndices, coefficents, numRows);
+ }
+
+
+ @Override
+ protected void computeRowMxx(double[] c, Builtin builtin, int rl, int ru, double[] preAgg) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public CompressionType getCompType() {
+ return CompressionType.LinearFunctional;
+ }
+
+ @Override
+ public ColGroupType getColGroupType() {
+ return ColGroupType.LinearFunctional;
+ }
+
+ @Override
+ public double getMin() {
+ double min = Double.POSITIVE_INFINITY;
+
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ if(slope >= 0 && (intercept + slope) < min) {
+ min = intercept + slope;
+ }
+ else if(slope < 0 && (intercept + _numRows * slope) < min) {
+ min = intercept + _numRows * slope;
+ }
+ }
+
+ return min;
+ }
+
+ @Override
+ public double getMax() {
+ double max = Double.NEGATIVE_INFINITY;
+
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ if(slope >= 0 && (intercept + _numRows * slope) > max) {
+ max = intercept + _numRows * slope;
+ }
+ else if(slope < 0 && (intercept + slope) > max) {
+ max = intercept + slope;
+ }
+ }
+
+ return max;
+ }
+
+ @Override
+ public void decompressToDenseBlock(DenseBlock db, int rl, int ru, int offR, int offC) {
+ int offT = rl + offR;
+ final int nCol = _colIndexes.length;
+ int offS = rl * nCol;
+ for(int row = rl; row < ru; row++, offT++, offS += nCol) {
+ final double[] c = db.values(offT);
+ final int off = db.pos(offT) + offC;
+ for(int j = 0; j < nCol; j++)
+ c[off + _colIndexes[j]] += getIdx(row, j);
+ }
+ }
+
+ @Override
+ public void decompressToSparseBlock(SparseBlock ret, int rl, int ru, int offR, int offC) {
+ final int nCol = _colIndexes.length;
+ for(int i = rl, offT = rl + offR; i < ru; i++, offT++) {
+ for(int j = 0; j < nCol; j++)
+ ret.append(offT, _colIndexes[j] + offC, getIdx(i, j));
+ }
+ }
+
+ @Override
+ public double getIdx(int r, int colIdx) {
+ return _coefficents[0][colIdx] + _coefficents[1][colIdx] * (r + 1);
+ }
+
+ @Override
+ public AColGroup scalarOperation(ScalarOperator op) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup unaryOperation(UnaryOperator op) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup binaryRowOpLeft(BinaryOperator op, double[] v, boolean isRowSafe) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup binaryRowOpRight(BinaryOperator op, double[] v, boolean isRowSafe) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected double computeMxx(double c, Builtin builtin) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected void computeColMxx(double[] c, Builtin builtin) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected void computeSum(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[0] += nRows * (intercept + (nRows + 1) * slope / 2);
+ }
+ }
+
+ @Override
+ public void computeColSums(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[_colIndexes[col]] += nRows * (intercept + (nRows + 1) * slope / 2);
+ }
+ }
+
+ @Override
+ protected void computeSumSq(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[0] += nRows * (Math.pow(intercept, 2) + (nRows + 1) * slope * intercept +
+ (nRows + 1) * (2 * nRows + 1) * Math.pow(slope, 2) / 6);
+ }
+ }
+
+ @Override
+ protected void computeColSumsSq(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[_colIndexes[col]] += nRows * (Math.pow(intercept, 2) + (nRows + 1) * slope * intercept +
+ (nRows + 1) * (2 * nRows + 1) * Math.pow(slope, 2) / 6);
+ }
+ }
+
+ @Override
+ protected void computeRowSums(double[] c, int rl, int ru, double[] preAgg) {
+ double intercept_sum = 0;
+ for(double intercept : _coefficents[0])
+ intercept_sum += intercept;
+
+ double slope_sum = 0;
+ for(double slope : _coefficents[1])
+ slope_sum += slope;
+
+ for(int rix = rl; rix < ru; rix++)
+ c[rix] += intercept_sum + slope_sum * (rix + 1);
+ }
+
+ @Override
+ public int getNumValues() {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup rightMultByMatrix(MatrixBlock right) {
+ final int nColR = right.getNumColumns();
+ final int[] outputCols = Util.genColsIndices(nColR);
+
+ MatrixBlock result = new MatrixBlock(_numRows, nColR, false);
+ for(int j = 0; j < nColR; j++) {
+ double bias_accum = 0.0;
+ double slope_accum = 0.0;
+
+ for(int c = 0; c < _colIndexes.length; c++) {
+ bias_accum += right.getValue(_colIndexes[c], j) * _coefficents[0][c];
+ slope_accum += right.getValue(_colIndexes[c], j) * _coefficents[1][c];
+ }
+
+ for(int r = 0; r < _numRows; r++) {
+ result.setValue(r, j, bias_accum + (r+1) * slope_accum);
+ }
+ }
+
+ // returns an uncompressed ColGroup
+ return ColGroupUncompressed.create(result, outputCols);
+ }
+
+ @Override
+ public void tsmm(double[] ret, int numColumns, int nRows) {
+ // runs in O(tCol^2) since dot-products take O(1) time to compute when both vectors are linearly compressed
+ final int tCol = _colIndexes.length;
+
+ final double sumIndices = nRows * (nRows + 1)/2.0;
+ final double sumSquaredIndices = nRows * (nRows + 1) * (2*nRows + 1)/6.0;
+ for(int row = 0, offTmp = 0; row < tCol; row++, offTmp += tCol) {
+ final double alpha1 = nRows * _coefficents[0][row] + sumIndices * _coefficents[1][row];
+ final double alpha2 = sumIndices * _coefficents[0][row] + sumSquaredIndices * _coefficents[1][row];
+ final int offRet = _colIndexes[row] * numColumns;
+ for(int col = row; col < tCol; col++) {
+ ret[offRet + _colIndexes[col]] += alpha1 * _coefficents[0][col] + alpha2 * _coefficents[1][col];
+ }
+ }
+ }
+
+ @Override
+ public void leftMultByMatrixNoPreAgg(MatrixBlock matrix, MatrixBlock result, int rl, int ru, int cl, int cu) {
+ throw new DMLCompressionException("This method should never be called");
+ }
+
+ @Override
+ public void leftMultByAColGroup(AColGroup lhs, MatrixBlock result) {
+ if(lhs instanceof ColGroupEmpty) {
+ return;
+ }
+
+ MatrixBlock tmpRet = new MatrixBlock(lhs.getNumCols(), _colIndexes.length, 0);
+
+ if(lhs instanceof ColGroupUncompressed) {
+ ColGroupUncompressed lhsUC = (ColGroupUncompressed) lhs;
+ int numRowsLeft = lhsUC.getData().getNumRows();
+
+ double[] colSumsAndWeightedColSums = new double[2 * lhs.getNumCols()];
+ for(int j = 0, offTmp = 0; j < lhs.getNumCols(); j++, offTmp += 2) {
+ for(int i = 0; i < numRowsLeft; i++) {
+ colSumsAndWeightedColSums[offTmp] += lhs.getIdx(i, j);
+ colSumsAndWeightedColSums[offTmp + 1] += (i+1) * lhs.getIdx(i, j);
+ }
+ }
+
+ MatrixBlock sumMatrix = new MatrixBlock(lhs.getNumCols(), 2, colSumsAndWeightedColSums);
+ MatrixBlock coefficientMatrix = DataConverter.convertToMatrixBlock(_coefficents);
+
+ LibMatrixMult.matrixMult(sumMatrix, coefficientMatrix, tmpRet);
+ } else if(lhs instanceof ColGroupLinearFunctional) {
+ ColGroupLinearFunctional lhsLF = (ColGroupLinearFunctional) lhs;
+
+ final double sumIndices = _numRows * (_numRows + 1)/2.0;
+ final double sumSquaredIndices = _numRows * (_numRows + 1) * (2*_numRows + 1)/6.0;
+
+ MatrixBlock weightMatrix = new MatrixBlock(2, 2, new double[] {_numRows, sumIndices, sumIndices, sumSquaredIndices});
+ MatrixBlock coefficientMatrixLhs = DataConverter.convertToMatrixBlock(lhsLF._coefficents);
+ MatrixBlock coefficientMatrixRhs = DataConverter.convertToMatrixBlock(_coefficents);
+
+ coefficientMatrixLhs = LibMatrixReorg.transposeInPlace(coefficientMatrixLhs,
+ InfrastructureAnalyzer.getLocalParallelism());
+
+ // We simply compute a matrix multiplication chain in coefficient space, i.e.,
+ // t(L) %*% R = t(coeff(L)) %*% W %*% coeff(R)
+ // where W is a weight matrix capturing the size of the shared dimension (weightMatrix above)
+ // and coeff(X) denotes the 2 x n matrix of the m x n matrix X.
+ MatrixBlock tmp = new MatrixBlock(lhs.getNumCols(), 2, false);
+ LibMatrixMult.matrixMult(coefficientMatrixLhs, weightMatrix, tmp);
+ LibMatrixMult.matrixMult(tmp, coefficientMatrixRhs, tmpRet);
+ } else if(lhs instanceof APreAgg) {
+ // TODO: implement
+ throw new NotImplementedException();
+ } else {
+ throw new NotImplementedException();
+ }
+
+ final double[] resV = result.getDenseBlockValues();
+ if(tmpRet.isEmpty())
+ return;
+ else if(tmpRet.isInSparseFormat()) {
+ SparseBlock sb = tmpRet.getSparseBlock();
+ for(int row = 0; row < lhs._colIndexes.length; row++) {
+ if(sb.isEmpty(row))
+ continue;
+ final int apos = sb.pos(row);
+ final int alen = sb.size(row) + apos;
+ final int[] aix = sb.indexes(row);
+ final double[] avals = sb.values(row);
+ final int offRes = lhs._colIndexes[row] * result.getNumColumns();
+ for(int col = apos; col < alen; col++)
+ resV[offRes + _colIndexes[aix[col]]] += avals[col];
+ }
+ }
+ else {
+ double[] tmpRetV = tmpRet.getDenseBlockValues();
+ for(int row = 0; row < lhs.getNumCols(); row++) {
+ final int offRes = lhs._colIndexes[row] * result.getNumColumns();
+ final int offTmp = row * getNumCols();
+ for(int col = 0; col < getNumCols(); col++) {
+ resV[offRes + _colIndexes[col]] += tmpRetV[offTmp + col];
+ }
+ }
+ }
+ }
+
+ @Override
+ public void tsmmAColGroup(AColGroup other, MatrixBlock result) {
+ throw new DMLCompressionException("Should not be called");
+ }
+
+ @Override
+ protected AColGroup sliceSingleColumn(int idx) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected AColGroup sliceMultiColumns(int idStart, int idEnd, int[] outputCols) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup copy() {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public boolean containsValue(double pattern) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public long getNumberNonZeros(int nRows) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup replace(double pattern, double replace) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public void readFields(DataInput in) throws IOException {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public void write(DataOutput out) throws IOException {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public long getExactSizeOnDisk() {
+ long ret = super.getExactSizeOnDisk();
+ ret += _coefficents[0].length * _coefficents.length * 8L;
Review Comment:
here similarly to the ColGroupSizes function the calculation is wrong.
##########
src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupLinearFunctional.java:
##########
@@ -0,0 +1,516 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.sysds.runtime.compress.colgroup;
+
+import org.apache.commons.lang.NotImplementedException;
+import org.apache.sysds.runtime.compress.DMLCompressionException;
+import org.apache.sysds.runtime.compress.cost.ComputationCostEstimator;
+import org.apache.sysds.runtime.compress.utils.Util;
+import org.apache.sysds.runtime.controlprogram.parfor.stat.InfrastructureAnalyzer;
+import org.apache.sysds.runtime.data.DenseBlock;
+import org.apache.sysds.runtime.data.SparseBlock;
+import org.apache.sysds.runtime.functionobjects.Builtin;
+import org.apache.sysds.runtime.instructions.cp.CM_COV_Object;
+import org.apache.sysds.runtime.matrix.data.LibMatrixMult;
+import org.apache.sysds.runtime.matrix.data.LibMatrixReorg;
+import org.apache.sysds.runtime.matrix.data.MatrixBlock;
+import org.apache.sysds.runtime.matrix.operators.BinaryOperator;
+import org.apache.sysds.runtime.matrix.operators.CMOperator;
+import org.apache.sysds.runtime.matrix.operators.ScalarOperator;
+import org.apache.sysds.runtime.matrix.operators.UnaryOperator;
+import org.apache.sysds.runtime.util.DataConverter;
+
+import java.io.DataInput;
+import java.io.DataOutput;
+import java.io.IOException;
+import java.util.Arrays;
+
+public class ColGroupLinearFunctional extends AColGroupCompressed {
+
+ private static final long serialVersionUID = -2811822570758221975L;
+
+ protected double[][] _coefficents;
+
+ protected int _numRows;
+
+ /** Constructor for serialization */
+ protected ColGroupLinearFunctional() {
+ super();
+ }
+
+ /**
+ * Constructs a Linear Functional Column Group that compresses its content using a linear functional.
+ *
+ * @param colIndices The Column indexes for the column group.
+ * @param coefficents 2D-Array where coefficients[0] is the list of intercepts and coefficients[1] the list of slopes.
+ * @param numRows Number of rows encoded within this column group.
+ */
+ private ColGroupLinearFunctional(int[] colIndices, double[][] coefficents, int numRows) {
+ super(colIndices);
+ this._coefficents = coefficents;
+ this._numRows = numRows;
+ }
+
+ /**
+ * Generate a linear functional column group.
+ *
+ * @param colIndices The specific column indexes that is contained in this column group.
+ * @param coefficents 2D-Array where coefficients[0] is the list of intercepts and coefficients[1] the list of slopes.
+ * @param numRows Number of rows encoded within this column group.
+ * @return A LinearFunctional column group.
+ */
+ public static AColGroup create(int[] colIndices, double[][] coefficents, int numRows) {
+ if(coefficents.length != 2 || colIndices.length != coefficents[0].length)
+ throw new DMLCompressionException("Invalid size of values compared to columns");
+ return new ColGroupLinearFunctional(colIndices, coefficents, numRows);
+ }
+
+
+ @Override
+ protected void computeRowMxx(double[] c, Builtin builtin, int rl, int ru, double[] preAgg) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public CompressionType getCompType() {
+ return CompressionType.LinearFunctional;
+ }
+
+ @Override
+ public ColGroupType getColGroupType() {
+ return ColGroupType.LinearFunctional;
+ }
+
+ @Override
+ public double getMin() {
+ double min = Double.POSITIVE_INFINITY;
+
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ if(slope >= 0 && (intercept + slope) < min) {
+ min = intercept + slope;
+ }
+ else if(slope < 0 && (intercept + _numRows * slope) < min) {
+ min = intercept + _numRows * slope;
+ }
+ }
+
+ return min;
+ }
+
+ @Override
+ public double getMax() {
+ double max = Double.NEGATIVE_INFINITY;
+
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ if(slope >= 0 && (intercept + _numRows * slope) > max) {
+ max = intercept + _numRows * slope;
+ }
+ else if(slope < 0 && (intercept + slope) > max) {
+ max = intercept + slope;
+ }
+ }
+
+ return max;
+ }
+
+ @Override
+ public void decompressToDenseBlock(DenseBlock db, int rl, int ru, int offR, int offC) {
+ int offT = rl + offR;
+ final int nCol = _colIndexes.length;
+ int offS = rl * nCol;
+ for(int row = rl; row < ru; row++, offT++, offS += nCol) {
+ final double[] c = db.values(offT);
+ final int off = db.pos(offT) + offC;
+ for(int j = 0; j < nCol; j++)
+ c[off + _colIndexes[j]] += getIdx(row, j);
+ }
+ }
+
+ @Override
+ public void decompressToSparseBlock(SparseBlock ret, int rl, int ru, int offR, int offC) {
+ final int nCol = _colIndexes.length;
+ for(int i = rl, offT = rl + offR; i < ru; i++, offT++) {
+ for(int j = 0; j < nCol; j++)
+ ret.append(offT, _colIndexes[j] + offC, getIdx(i, j));
+ }
+ }
+
+ @Override
+ public double getIdx(int r, int colIdx) {
+ return _coefficents[0][colIdx] + _coefficents[1][colIdx] * (r + 1);
+ }
+
+ @Override
+ public AColGroup scalarOperation(ScalarOperator op) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup unaryOperation(UnaryOperator op) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup binaryRowOpLeft(BinaryOperator op, double[] v, boolean isRowSafe) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup binaryRowOpRight(BinaryOperator op, double[] v, boolean isRowSafe) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected double computeMxx(double c, Builtin builtin) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected void computeColMxx(double[] c, Builtin builtin) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected void computeSum(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[0] += nRows * (intercept + (nRows + 1) * slope / 2);
+ }
+ }
+
+ @Override
+ public void computeColSums(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[_colIndexes[col]] += nRows * (intercept + (nRows + 1) * slope / 2);
+ }
+ }
+
+ @Override
+ protected void computeSumSq(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[0] += nRows * (Math.pow(intercept, 2) + (nRows + 1) * slope * intercept +
+ (nRows + 1) * (2 * nRows + 1) * Math.pow(slope, 2) / 6);
+ }
+ }
+
+ @Override
+ protected void computeColSumsSq(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[_colIndexes[col]] += nRows * (Math.pow(intercept, 2) + (nRows + 1) * slope * intercept +
+ (nRows + 1) * (2 * nRows + 1) * Math.pow(slope, 2) / 6);
+ }
+ }
+
+ @Override
+ protected void computeRowSums(double[] c, int rl, int ru, double[] preAgg) {
+ double intercept_sum = 0;
+ for(double intercept : _coefficents[0])
+ intercept_sum += intercept;
+
+ double slope_sum = 0;
+ for(double slope : _coefficents[1])
+ slope_sum += slope;
+
+ for(int rix = rl; rix < ru; rix++)
+ c[rix] += intercept_sum + slope_sum * (rix + 1);
+ }
+
+ @Override
+ public int getNumValues() {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup rightMultByMatrix(MatrixBlock right) {
+ final int nColR = right.getNumColumns();
+ final int[] outputCols = Util.genColsIndices(nColR);
+
+ MatrixBlock result = new MatrixBlock(_numRows, nColR, false);
+ for(int j = 0; j < nColR; j++) {
+ double bias_accum = 0.0;
+ double slope_accum = 0.0;
+
+ for(int c = 0; c < _colIndexes.length; c++) {
+ bias_accum += right.getValue(_colIndexes[c], j) * _coefficents[0][c];
+ slope_accum += right.getValue(_colIndexes[c], j) * _coefficents[1][c];
+ }
+
+ for(int r = 0; r < _numRows; r++) {
+ result.setValue(r, j, bias_accum + (r+1) * slope_accum);
+ }
+ }
+
+ // returns an uncompressed ColGroup
+ return ColGroupUncompressed.create(result, outputCols);
+ }
+
+ @Override
+ public void tsmm(double[] ret, int numColumns, int nRows) {
+ // runs in O(tCol^2) since dot-products take O(1) time to compute when both vectors are linearly compressed
+ final int tCol = _colIndexes.length;
+
+ final double sumIndices = nRows * (nRows + 1)/2.0;
+ final double sumSquaredIndices = nRows * (nRows + 1) * (2*nRows + 1)/6.0;
+ for(int row = 0, offTmp = 0; row < tCol; row++, offTmp += tCol) {
+ final double alpha1 = nRows * _coefficents[0][row] + sumIndices * _coefficents[1][row];
+ final double alpha2 = sumIndices * _coefficents[0][row] + sumSquaredIndices * _coefficents[1][row];
+ final int offRet = _colIndexes[row] * numColumns;
+ for(int col = row; col < tCol; col++) {
+ ret[offRet + _colIndexes[col]] += alpha1 * _coefficents[0][col] + alpha2 * _coefficents[1][col];
+ }
+ }
+ }
+
+ @Override
+ public void leftMultByMatrixNoPreAgg(MatrixBlock matrix, MatrixBlock result, int rl, int ru, int cl, int cu) {
+ throw new DMLCompressionException("This method should never be called");
+ }
+
+ @Override
+ public void leftMultByAColGroup(AColGroup lhs, MatrixBlock result) {
+ if(lhs instanceof ColGroupEmpty) {
+ return;
+ }
+
+ MatrixBlock tmpRet = new MatrixBlock(lhs.getNumCols(), _colIndexes.length, 0);
+
+ if(lhs instanceof ColGroupUncompressed) {
+ ColGroupUncompressed lhsUC = (ColGroupUncompressed) lhs;
+ int numRowsLeft = lhsUC.getData().getNumRows();
+
+ double[] colSumsAndWeightedColSums = new double[2 * lhs.getNumCols()];
+ for(int j = 0, offTmp = 0; j < lhs.getNumCols(); j++, offTmp += 2) {
+ for(int i = 0; i < numRowsLeft; i++) {
+ colSumsAndWeightedColSums[offTmp] += lhs.getIdx(i, j);
+ colSumsAndWeightedColSums[offTmp + 1] += (i+1) * lhs.getIdx(i, j);
+ }
+ }
+
+ MatrixBlock sumMatrix = new MatrixBlock(lhs.getNumCols(), 2, colSumsAndWeightedColSums);
+ MatrixBlock coefficientMatrix = DataConverter.convertToMatrixBlock(_coefficents);
+
+ LibMatrixMult.matrixMult(sumMatrix, coefficientMatrix, tmpRet);
+ } else if(lhs instanceof ColGroupLinearFunctional) {
+ ColGroupLinearFunctional lhsLF = (ColGroupLinearFunctional) lhs;
+
+ final double sumIndices = _numRows * (_numRows + 1)/2.0;
+ final double sumSquaredIndices = _numRows * (_numRows + 1) * (2*_numRows + 1)/6.0;
+
+ MatrixBlock weightMatrix = new MatrixBlock(2, 2, new double[] {_numRows, sumIndices, sumIndices, sumSquaredIndices});
+ MatrixBlock coefficientMatrixLhs = DataConverter.convertToMatrixBlock(lhsLF._coefficents);
+ MatrixBlock coefficientMatrixRhs = DataConverter.convertToMatrixBlock(_coefficents);
+
+ coefficientMatrixLhs = LibMatrixReorg.transposeInPlace(coefficientMatrixLhs,
+ InfrastructureAnalyzer.getLocalParallelism());
+
+ // We simply compute a matrix multiplication chain in coefficient space, i.e.,
+ // t(L) %*% R = t(coeff(L)) %*% W %*% coeff(R)
+ // where W is a weight matrix capturing the size of the shared dimension (weightMatrix above)
+ // and coeff(X) denotes the 2 x n matrix of the m x n matrix X.
+ MatrixBlock tmp = new MatrixBlock(lhs.getNumCols(), 2, false);
+ LibMatrixMult.matrixMult(coefficientMatrixLhs, weightMatrix, tmp);
+ LibMatrixMult.matrixMult(tmp, coefficientMatrixRhs, tmpRet);
+ } else if(lhs instanceof APreAgg) {
+ // TODO: implement
+ throw new NotImplementedException();
+ } else {
+ throw new NotImplementedException();
+ }
+
+ final double[] resV = result.getDenseBlockValues();
+ if(tmpRet.isEmpty())
+ return;
+ else if(tmpRet.isInSparseFormat()) {
+ SparseBlock sb = tmpRet.getSparseBlock();
+ for(int row = 0; row < lhs._colIndexes.length; row++) {
+ if(sb.isEmpty(row))
+ continue;
+ final int apos = sb.pos(row);
+ final int alen = sb.size(row) + apos;
+ final int[] aix = sb.indexes(row);
+ final double[] avals = sb.values(row);
+ final int offRes = lhs._colIndexes[row] * result.getNumColumns();
+ for(int col = apos; col < alen; col++)
+ resV[offRes + _colIndexes[aix[col]]] += avals[col];
+ }
+ }
+ else {
+ double[] tmpRetV = tmpRet.getDenseBlockValues();
+ for(int row = 0; row < lhs.getNumCols(); row++) {
+ final int offRes = lhs._colIndexes[row] * result.getNumColumns();
+ final int offTmp = row * getNumCols();
+ for(int col = 0; col < getNumCols(); col++) {
+ resV[offRes + _colIndexes[col]] += tmpRetV[offTmp + col];
+ }
+ }
+ }
+ }
+
+ @Override
+ public void tsmmAColGroup(AColGroup other, MatrixBlock result) {
+ throw new DMLCompressionException("Should not be called");
+ }
+
+ @Override
+ protected AColGroup sliceSingleColumn(int idx) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected AColGroup sliceMultiColumns(int idStart, int idEnd, int[] outputCols) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup copy() {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public boolean containsValue(double pattern) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public long getNumberNonZeros(int nRows) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup replace(double pattern, double replace) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public void readFields(DataInput in) throws IOException {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public void write(DataOutput out) throws IOException {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public long getExactSizeOnDisk() {
+ long ret = super.getExactSizeOnDisk();
+ ret += _coefficents[0].length * _coefficents.length * 8L;
+ ret += 4L; // _numRows
+ return ret;
+ }
+
+ @Override
+ protected void computeProduct(double[] c, int nRows) {
+ c[0] = 1;
+ for(int colIndex : _colIndexes) {
+ double intercept = _coefficents[0][colIndex];
+ double slope = _coefficents[1][colIndex];
+ for(int i = 0; i < nRows; i++) {
+ c[0] *= intercept + slope * (i + 1);
+ }
+ }
+ }
+
+ @Override
+ protected void computeRowProduct(double[] c, int rl, int ru, double[] preAgg) {
+ for(int rix = rl; rix < ru; rix++) {
+ c[rix] = 1;
+ for(int colIndex : _colIndexes) {
+ double intercept = _coefficents[0][colIndex];
+ double slope = _coefficents[1][colIndex];
+ c[rix] *= intercept + slope * (rix + 1);
+ }
+ }
+ }
+
+ @Override
+ protected void computeColProduct(double[] c, int nRows) {
+ for(int colIndex : _colIndexes) {
+ c[colIndex] = 1;
+ double intercept = _coefficents[0][colIndex];
+ double slope = _coefficents[1][colIndex];
+ for(int i = 0; i < nRows; i++) {
+ c[colIndex] *= intercept + slope * (i + 1);
+ }
+ }
+ }
+
+ @Override
+ protected double[] preAggSumRows() {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected double[] preAggSumSqRows() {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected double[] preAggProductRows() {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected double[] preAggBuiltinRows(Builtin builtin) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public long estimateInMemorySize() {
+ return ColGroupSizes.estimateInMemorySizeLinearFunctional(getNumCols());
+ }
+
+ @Override
+ public CM_COV_Object centralMoment(CMOperator op, int nRows) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup rexpandCols(int max, boolean ignore, boolean cast, int nRows) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public double getCost(ComputationCostEstimator e, int nRows) {
+ final int nCols = getNumCols();
+ // We store 2 tuples in this column group, namely intercepts and slopes
+ return e.getCost(nRows, nRows, nCols, 2, 1.0);
+ }
+
+ @Override
+ public String toString() {
+ StringBuilder sb = new StringBuilder();
+ sb.append(super.toString());
+ sb.append(String.format("\n%15s", " Intercepts: \t" + Arrays.toString(_coefficents[0])));
Review Comment:
if you format it, don't use `\t` since we want it to align based on the `%15s` not what tab length it fit after.
##########
src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupLinearFunctional.java:
##########
@@ -0,0 +1,516 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.sysds.runtime.compress.colgroup;
+
+import org.apache.commons.lang.NotImplementedException;
+import org.apache.sysds.runtime.compress.DMLCompressionException;
+import org.apache.sysds.runtime.compress.cost.ComputationCostEstimator;
+import org.apache.sysds.runtime.compress.utils.Util;
+import org.apache.sysds.runtime.controlprogram.parfor.stat.InfrastructureAnalyzer;
+import org.apache.sysds.runtime.data.DenseBlock;
+import org.apache.sysds.runtime.data.SparseBlock;
+import org.apache.sysds.runtime.functionobjects.Builtin;
+import org.apache.sysds.runtime.instructions.cp.CM_COV_Object;
+import org.apache.sysds.runtime.matrix.data.LibMatrixMult;
+import org.apache.sysds.runtime.matrix.data.LibMatrixReorg;
+import org.apache.sysds.runtime.matrix.data.MatrixBlock;
+import org.apache.sysds.runtime.matrix.operators.BinaryOperator;
+import org.apache.sysds.runtime.matrix.operators.CMOperator;
+import org.apache.sysds.runtime.matrix.operators.ScalarOperator;
+import org.apache.sysds.runtime.matrix.operators.UnaryOperator;
+import org.apache.sysds.runtime.util.DataConverter;
+
+import java.io.DataInput;
+import java.io.DataOutput;
+import java.io.IOException;
+import java.util.Arrays;
+
+public class ColGroupLinearFunctional extends AColGroupCompressed {
+
+ private static final long serialVersionUID = -2811822570758221975L;
+
+ protected double[][] _coefficents;
+
+ protected int _numRows;
+
+ /** Constructor for serialization */
+ protected ColGroupLinearFunctional() {
+ super();
+ }
+
+ /**
+ * Constructs a Linear Functional Column Group that compresses its content using a linear functional.
+ *
+ * @param colIndices The Column indexes for the column group.
+ * @param coefficents 2D-Array where coefficients[0] is the list of intercepts and coefficients[1] the list of slopes.
+ * @param numRows Number of rows encoded within this column group.
+ */
+ private ColGroupLinearFunctional(int[] colIndices, double[][] coefficents, int numRows) {
+ super(colIndices);
+ this._coefficents = coefficents;
+ this._numRows = numRows;
+ }
+
+ /**
+ * Generate a linear functional column group.
+ *
+ * @param colIndices The specific column indexes that is contained in this column group.
+ * @param coefficents 2D-Array where coefficients[0] is the list of intercepts and coefficients[1] the list of slopes.
+ * @param numRows Number of rows encoded within this column group.
+ * @return A LinearFunctional column group.
+ */
+ public static AColGroup create(int[] colIndices, double[][] coefficents, int numRows) {
+ if(coefficents.length != 2 || colIndices.length != coefficents[0].length)
+ throw new DMLCompressionException("Invalid size of values compared to columns");
+ return new ColGroupLinearFunctional(colIndices, coefficents, numRows);
+ }
+
+
+ @Override
+ protected void computeRowMxx(double[] c, Builtin builtin, int rl, int ru, double[] preAgg) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public CompressionType getCompType() {
+ return CompressionType.LinearFunctional;
+ }
+
+ @Override
+ public ColGroupType getColGroupType() {
+ return ColGroupType.LinearFunctional;
+ }
+
+ @Override
+ public double getMin() {
+ double min = Double.POSITIVE_INFINITY;
+
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ if(slope >= 0 && (intercept + slope) < min) {
+ min = intercept + slope;
+ }
+ else if(slope < 0 && (intercept + _numRows * slope) < min) {
+ min = intercept + _numRows * slope;
+ }
+ }
+
+ return min;
+ }
+
+ @Override
+ public double getMax() {
+ double max = Double.NEGATIVE_INFINITY;
+
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ if(slope >= 0 && (intercept + _numRows * slope) > max) {
+ max = intercept + _numRows * slope;
+ }
+ else if(slope < 0 && (intercept + slope) > max) {
+ max = intercept + slope;
+ }
+ }
+
+ return max;
+ }
+
+ @Override
+ public void decompressToDenseBlock(DenseBlock db, int rl, int ru, int offR, int offC) {
+ int offT = rl + offR;
+ final int nCol = _colIndexes.length;
+ int offS = rl * nCol;
+ for(int row = rl; row < ru; row++, offT++, offS += nCol) {
+ final double[] c = db.values(offT);
+ final int off = db.pos(offT) + offC;
+ for(int j = 0; j < nCol; j++)
+ c[off + _colIndexes[j]] += getIdx(row, j);
+ }
+ }
+
+ @Override
+ public void decompressToSparseBlock(SparseBlock ret, int rl, int ru, int offR, int offC) {
+ final int nCol = _colIndexes.length;
+ for(int i = rl, offT = rl + offR; i < ru; i++, offT++) {
+ for(int j = 0; j < nCol; j++)
+ ret.append(offT, _colIndexes[j] + offC, getIdx(i, j));
+ }
+ }
+
+ @Override
+ public double getIdx(int r, int colIdx) {
+ return _coefficents[0][colIdx] + _coefficents[1][colIdx] * (r + 1);
+ }
+
+ @Override
+ public AColGroup scalarOperation(ScalarOperator op) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup unaryOperation(UnaryOperator op) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup binaryRowOpLeft(BinaryOperator op, double[] v, boolean isRowSafe) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup binaryRowOpRight(BinaryOperator op, double[] v, boolean isRowSafe) {
+ throw new NotImplementedException();
Review Comment:
if you do the scalar operation, then here the same operations would be easy.
##########
src/main/java/org/apache/sysds/runtime/compress/colgroup/functional/LinearRegression.java:
##########
@@ -0,0 +1,57 @@
+package org.apache.sysds.runtime.compress.colgroup.functional;
+
+import org.apache.sysds.runtime.compress.DMLCompressionException;
+import org.apache.sysds.runtime.compress.readers.ReaderColumnSelection;
+import org.apache.sysds.runtime.compress.utils.DblArray;
+import org.apache.sysds.runtime.matrix.data.MatrixBlock;
+
+public class LinearRegression {
+ public static double[][] regressMatrixBlock(MatrixBlock rawBlock, int[] colIndexes, boolean transposed) {
+ final int nRows = transposed ? rawBlock.getNumColumns() : rawBlock.getNumRows();
+
+ if(nRows <= 1) {
+ throw new DMLCompressionException("At least 2 data points are required to fit a linear function.");
+ }
+
+ if(colIndexes.length < 1) {
Review Comment:
else if
##########
src/main/java/org/apache/sysds/runtime/compress/colgroup/functional/LinearRegression.java:
##########
@@ -0,0 +1,57 @@
+package org.apache.sysds.runtime.compress.colgroup.functional;
+
+import org.apache.sysds.runtime.compress.DMLCompressionException;
+import org.apache.sysds.runtime.compress.readers.ReaderColumnSelection;
+import org.apache.sysds.runtime.compress.utils.DblArray;
+import org.apache.sysds.runtime.matrix.data.MatrixBlock;
+
+public class LinearRegression {
+ public static double[][] regressMatrixBlock(MatrixBlock rawBlock, int[] colIndexes, boolean transposed) {
Review Comment:
i would suggest you linearize the allocation to a single double[] and decide how to index into it for the different values.
(note the comment on size later)
##########
src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupLinearFunctional.java:
##########
@@ -0,0 +1,516 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.sysds.runtime.compress.colgroup;
+
+import org.apache.commons.lang.NotImplementedException;
+import org.apache.sysds.runtime.compress.DMLCompressionException;
+import org.apache.sysds.runtime.compress.cost.ComputationCostEstimator;
+import org.apache.sysds.runtime.compress.utils.Util;
+import org.apache.sysds.runtime.controlprogram.parfor.stat.InfrastructureAnalyzer;
+import org.apache.sysds.runtime.data.DenseBlock;
+import org.apache.sysds.runtime.data.SparseBlock;
+import org.apache.sysds.runtime.functionobjects.Builtin;
+import org.apache.sysds.runtime.instructions.cp.CM_COV_Object;
+import org.apache.sysds.runtime.matrix.data.LibMatrixMult;
+import org.apache.sysds.runtime.matrix.data.LibMatrixReorg;
+import org.apache.sysds.runtime.matrix.data.MatrixBlock;
+import org.apache.sysds.runtime.matrix.operators.BinaryOperator;
+import org.apache.sysds.runtime.matrix.operators.CMOperator;
+import org.apache.sysds.runtime.matrix.operators.ScalarOperator;
+import org.apache.sysds.runtime.matrix.operators.UnaryOperator;
+import org.apache.sysds.runtime.util.DataConverter;
+
+import java.io.DataInput;
+import java.io.DataOutput;
+import java.io.IOException;
+import java.util.Arrays;
+
+public class ColGroupLinearFunctional extends AColGroupCompressed {
+
+ private static final long serialVersionUID = -2811822570758221975L;
+
+ protected double[][] _coefficents;
+
+ protected int _numRows;
+
+ /** Constructor for serialization */
+ protected ColGroupLinearFunctional() {
+ super();
+ }
+
+ /**
+ * Constructs a Linear Functional Column Group that compresses its content using a linear functional.
+ *
+ * @param colIndices The Column indexes for the column group.
+ * @param coefficents 2D-Array where coefficients[0] is the list of intercepts and coefficients[1] the list of slopes.
+ * @param numRows Number of rows encoded within this column group.
+ */
+ private ColGroupLinearFunctional(int[] colIndices, double[][] coefficents, int numRows) {
+ super(colIndices);
+ this._coefficents = coefficents;
+ this._numRows = numRows;
+ }
+
+ /**
+ * Generate a linear functional column group.
+ *
+ * @param colIndices The specific column indexes that is contained in this column group.
+ * @param coefficents 2D-Array where coefficients[0] is the list of intercepts and coefficients[1] the list of slopes.
+ * @param numRows Number of rows encoded within this column group.
+ * @return A LinearFunctional column group.
+ */
+ public static AColGroup create(int[] colIndices, double[][] coefficents, int numRows) {
+ if(coefficents.length != 2 || colIndices.length != coefficents[0].length)
+ throw new DMLCompressionException("Invalid size of values compared to columns");
+ return new ColGroupLinearFunctional(colIndices, coefficents, numRows);
+ }
+
+
+ @Override
+ protected void computeRowMxx(double[] c, Builtin builtin, int rl, int ru, double[] preAgg) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public CompressionType getCompType() {
+ return CompressionType.LinearFunctional;
+ }
+
+ @Override
+ public ColGroupType getColGroupType() {
+ return ColGroupType.LinearFunctional;
+ }
+
+ @Override
+ public double getMin() {
+ double min = Double.POSITIVE_INFINITY;
+
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ if(slope >= 0 && (intercept + slope) < min) {
+ min = intercept + slope;
+ }
+ else if(slope < 0 && (intercept + _numRows * slope) < min) {
+ min = intercept + _numRows * slope;
+ }
+ }
+
+ return min;
+ }
+
+ @Override
+ public double getMax() {
+ double max = Double.NEGATIVE_INFINITY;
+
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ if(slope >= 0 && (intercept + _numRows * slope) > max) {
+ max = intercept + _numRows * slope;
+ }
+ else if(slope < 0 && (intercept + slope) > max) {
+ max = intercept + slope;
+ }
+ }
+
+ return max;
+ }
+
+ @Override
+ public void decompressToDenseBlock(DenseBlock db, int rl, int ru, int offR, int offC) {
+ int offT = rl + offR;
+ final int nCol = _colIndexes.length;
+ int offS = rl * nCol;
+ for(int row = rl; row < ru; row++, offT++, offS += nCol) {
+ final double[] c = db.values(offT);
+ final int off = db.pos(offT) + offC;
+ for(int j = 0; j < nCol; j++)
+ c[off + _colIndexes[j]] += getIdx(row, j);
+ }
+ }
+
+ @Override
+ public void decompressToSparseBlock(SparseBlock ret, int rl, int ru, int offR, int offC) {
+ final int nCol = _colIndexes.length;
+ for(int i = rl, offT = rl + offR; i < ru; i++, offT++) {
+ for(int j = 0; j < nCol; j++)
+ ret.append(offT, _colIndexes[j] + offC, getIdx(i, j));
+ }
+ }
+
+ @Override
+ public double getIdx(int r, int colIdx) {
+ return _coefficents[0][colIdx] + _coefficents[1][colIdx] * (r + 1);
+ }
+
+ @Override
+ public AColGroup scalarOperation(ScalarOperator op) {
+ throw new NotImplementedException();
Review Comment:
Plus, minus, mult and div should be very easy if you want to.
in all other cases just throw the NotImplementedException.
##########
src/test/java/org/apache/sysds/test/component/compress/functional/LinearRegressionTests.java:
##########
@@ -0,0 +1,43 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.sysds.test.component.compress.functional;
+
+import org.apache.sysds.runtime.compress.colgroup.functional.LinearRegression;
+import org.apache.sysds.runtime.matrix.data.MatrixBlock;
+import org.apache.sysds.runtime.util.DataConverter;
+import org.junit.Test;
+
+import static org.junit.Assert.assertArrayEquals;
+
+public class LinearRegressionTests {
+
+ @Test
+ public void testLinearRegression() {
Review Comment:
while this does test your implementation, it does not verify the different cases possible.
here use Parameterized testing as well, and add tests to verify your exceptions are properly thrown.
##########
src/test/java/org/apache/sysds/test/component/compress/colgroup/ColGroupLinearFunctionalTest.java:
##########
@@ -0,0 +1,547 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.sysds.test.component.compress.colgroup;
+
+import org.apache.commons.logging.Log;
+import org.apache.commons.logging.LogFactory;
+import org.apache.sysds.runtime.DMLRuntimeException;
+import org.apache.sysds.runtime.compress.CompressionSettings;
+import org.apache.sysds.runtime.compress.CompressionSettingsBuilder;
+import org.apache.sysds.runtime.compress.colgroup.AColGroup;
+import org.apache.sysds.runtime.compress.colgroup.ColGroupFactory;
+import org.apache.sysds.runtime.compress.colgroup.ColGroupUncompressed;
+import org.apache.sysds.runtime.compress.estim.CompressedSizeEstimatorExact;
+import org.apache.sysds.runtime.compress.estim.CompressedSizeInfo;
+import org.apache.sysds.runtime.compress.estim.CompressedSizeInfoColGroup;
+import org.apache.sysds.runtime.controlprogram.parfor.stat.InfrastructureAnalyzer;
+import org.apache.sysds.runtime.functionobjects.*;
+import org.apache.sysds.runtime.matrix.data.LibMatrixMult;
+import org.apache.sysds.runtime.matrix.data.LibMatrixReorg;
+import org.apache.sysds.runtime.matrix.data.MatrixBlock;
+import org.apache.sysds.runtime.matrix.operators.AggregateOperator;
+import org.apache.sysds.runtime.matrix.operators.AggregateUnaryOperator;
+import org.apache.sysds.runtime.util.DataConverter;
+import org.junit.Assert;
+import org.junit.Test;
+
+import java.util.EnumSet;
+import java.util.Random;
+
+public class ColGroupLinearFunctionalTest {
Review Comment:
you are making testing harder than it should be since you in each test case allocate a new compression and execute on this.
Instead make a constructor that contains take two column groups one AColgroup and another ColGroupLinearFunctional
then simply compare the output of each on various scenarios.
For inspiration:
https://github.com/apache/systemds/blob/926c676d6ea9dafd817b9254614fadcc0b175d3d/src/test/java/org/apache/sysds/test/component/compress/colgroup/ColGroupBase.java
and test:
https://github.com/apache/systemds/blob/926c676d6ea9dafd817b9254614fadcc0b175d3d/src/test/java/org/apache/sysds/test/component/compress/colgroup/ColGroupTest.java
These two files will be merged in shortly but currently are in a PR.
##########
src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupUncompressed.java:
##########
@@ -579,10 +579,10 @@ else if(tmpRet.isInSparseFormat()) {
}
else {
double[] tmpRetV = tmpRet.getDenseBlockValues();
- for(int row = 0; row < lhs._colIndexes.length; row++) {
+ for(int row = 0; row < lhs.getNumCols(); row++) {
final int offRes = lhs._colIndexes[row] * result.getNumColumns();
- final int offTmp = lhs._colIndexes.length * row;
- for(int col = 0; col < _colIndexes.length; col++) {
+ final int offTmp = row * getNumCols();
+ for(int col = 0; col < getNumCols(); col++) {
Review Comment:
:) i found this bug as well in my PR, but thanks for spotting it here as well.
##########
src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupLinearFunctional.java:
##########
@@ -0,0 +1,516 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.sysds.runtime.compress.colgroup;
+
+import org.apache.commons.lang.NotImplementedException;
+import org.apache.sysds.runtime.compress.DMLCompressionException;
+import org.apache.sysds.runtime.compress.cost.ComputationCostEstimator;
+import org.apache.sysds.runtime.compress.utils.Util;
+import org.apache.sysds.runtime.controlprogram.parfor.stat.InfrastructureAnalyzer;
+import org.apache.sysds.runtime.data.DenseBlock;
+import org.apache.sysds.runtime.data.SparseBlock;
+import org.apache.sysds.runtime.functionobjects.Builtin;
+import org.apache.sysds.runtime.instructions.cp.CM_COV_Object;
+import org.apache.sysds.runtime.matrix.data.LibMatrixMult;
+import org.apache.sysds.runtime.matrix.data.LibMatrixReorg;
+import org.apache.sysds.runtime.matrix.data.MatrixBlock;
+import org.apache.sysds.runtime.matrix.operators.BinaryOperator;
+import org.apache.sysds.runtime.matrix.operators.CMOperator;
+import org.apache.sysds.runtime.matrix.operators.ScalarOperator;
+import org.apache.sysds.runtime.matrix.operators.UnaryOperator;
+import org.apache.sysds.runtime.util.DataConverter;
+
+import java.io.DataInput;
+import java.io.DataOutput;
+import java.io.IOException;
+import java.util.Arrays;
+
+public class ColGroupLinearFunctional extends AColGroupCompressed {
+
+ private static final long serialVersionUID = -2811822570758221975L;
+
+ protected double[][] _coefficents;
+
+ protected int _numRows;
+
+ /** Constructor for serialization */
+ protected ColGroupLinearFunctional() {
+ super();
+ }
+
+ /**
+ * Constructs a Linear Functional Column Group that compresses its content using a linear functional.
+ *
+ * @param colIndices The Column indexes for the column group.
+ * @param coefficents 2D-Array where coefficients[0] is the list of intercepts and coefficients[1] the list of slopes.
+ * @param numRows Number of rows encoded within this column group.
+ */
+ private ColGroupLinearFunctional(int[] colIndices, double[][] coefficents, int numRows) {
+ super(colIndices);
+ this._coefficents = coefficents;
+ this._numRows = numRows;
+ }
+
+ /**
+ * Generate a linear functional column group.
+ *
+ * @param colIndices The specific column indexes that is contained in this column group.
+ * @param coefficents 2D-Array where coefficients[0] is the list of intercepts and coefficients[1] the list of slopes.
+ * @param numRows Number of rows encoded within this column group.
+ * @return A LinearFunctional column group.
+ */
+ public static AColGroup create(int[] colIndices, double[][] coefficents, int numRows) {
+ if(coefficents.length != 2 || colIndices.length != coefficents[0].length)
+ throw new DMLCompressionException("Invalid size of values compared to columns");
+ return new ColGroupLinearFunctional(colIndices, coefficents, numRows);
+ }
+
+
+ @Override
+ protected void computeRowMxx(double[] c, Builtin builtin, int rl, int ru, double[] preAgg) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public CompressionType getCompType() {
+ return CompressionType.LinearFunctional;
+ }
+
+ @Override
+ public ColGroupType getColGroupType() {
+ return ColGroupType.LinearFunctional;
+ }
+
+ @Override
+ public double getMin() {
+ double min = Double.POSITIVE_INFINITY;
+
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ if(slope >= 0 && (intercept + slope) < min) {
+ min = intercept + slope;
+ }
+ else if(slope < 0 && (intercept + _numRows * slope) < min) {
+ min = intercept + _numRows * slope;
+ }
+ }
+
+ return min;
+ }
+
+ @Override
+ public double getMax() {
+ double max = Double.NEGATIVE_INFINITY;
+
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ if(slope >= 0 && (intercept + _numRows * slope) > max) {
+ max = intercept + _numRows * slope;
+ }
+ else if(slope < 0 && (intercept + slope) > max) {
+ max = intercept + slope;
+ }
+ }
+
+ return max;
+ }
+
+ @Override
+ public void decompressToDenseBlock(DenseBlock db, int rl, int ru, int offR, int offC) {
+ int offT = rl + offR;
+ final int nCol = _colIndexes.length;
+ int offS = rl * nCol;
+ for(int row = rl; row < ru; row++, offT++, offS += nCol) {
+ final double[] c = db.values(offT);
+ final int off = db.pos(offT) + offC;
+ for(int j = 0; j < nCol; j++)
+ c[off + _colIndexes[j]] += getIdx(row, j);
+ }
+ }
+
+ @Override
+ public void decompressToSparseBlock(SparseBlock ret, int rl, int ru, int offR, int offC) {
+ final int nCol = _colIndexes.length;
+ for(int i = rl, offT = rl + offR; i < ru; i++, offT++) {
+ for(int j = 0; j < nCol; j++)
+ ret.append(offT, _colIndexes[j] + offC, getIdx(i, j));
+ }
+ }
+
+ @Override
+ public double getIdx(int r, int colIdx) {
+ return _coefficents[0][colIdx] + _coefficents[1][colIdx] * (r + 1);
+ }
+
+ @Override
+ public AColGroup scalarOperation(ScalarOperator op) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup unaryOperation(UnaryOperator op) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup binaryRowOpLeft(BinaryOperator op, double[] v, boolean isRowSafe) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup binaryRowOpRight(BinaryOperator op, double[] v, boolean isRowSafe) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected double computeMxx(double c, Builtin builtin) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected void computeColMxx(double[] c, Builtin builtin) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected void computeSum(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[0] += nRows * (intercept + (nRows + 1) * slope / 2);
+ }
+ }
+
+ @Override
+ public void computeColSums(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[_colIndexes[col]] += nRows * (intercept + (nRows + 1) * slope / 2);
+ }
+ }
+
+ @Override
+ protected void computeSumSq(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[0] += nRows * (Math.pow(intercept, 2) + (nRows + 1) * slope * intercept +
+ (nRows + 1) * (2 * nRows + 1) * Math.pow(slope, 2) / 6);
Review Comment:
uuh, slightly fancy. Maybe a comment would do.
##########
src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupLinearFunctional.java:
##########
@@ -0,0 +1,516 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.sysds.runtime.compress.colgroup;
+
+import org.apache.commons.lang.NotImplementedException;
+import org.apache.sysds.runtime.compress.DMLCompressionException;
+import org.apache.sysds.runtime.compress.cost.ComputationCostEstimator;
+import org.apache.sysds.runtime.compress.utils.Util;
+import org.apache.sysds.runtime.controlprogram.parfor.stat.InfrastructureAnalyzer;
+import org.apache.sysds.runtime.data.DenseBlock;
+import org.apache.sysds.runtime.data.SparseBlock;
+import org.apache.sysds.runtime.functionobjects.Builtin;
+import org.apache.sysds.runtime.instructions.cp.CM_COV_Object;
+import org.apache.sysds.runtime.matrix.data.LibMatrixMult;
+import org.apache.sysds.runtime.matrix.data.LibMatrixReorg;
+import org.apache.sysds.runtime.matrix.data.MatrixBlock;
+import org.apache.sysds.runtime.matrix.operators.BinaryOperator;
+import org.apache.sysds.runtime.matrix.operators.CMOperator;
+import org.apache.sysds.runtime.matrix.operators.ScalarOperator;
+import org.apache.sysds.runtime.matrix.operators.UnaryOperator;
+import org.apache.sysds.runtime.util.DataConverter;
+
+import java.io.DataInput;
+import java.io.DataOutput;
+import java.io.IOException;
+import java.util.Arrays;
+
+public class ColGroupLinearFunctional extends AColGroupCompressed {
+
+ private static final long serialVersionUID = -2811822570758221975L;
+
+ protected double[][] _coefficents;
+
+ protected int _numRows;
+
+ /** Constructor for serialization */
+ protected ColGroupLinearFunctional() {
+ super();
+ }
+
+ /**
+ * Constructs a Linear Functional Column Group that compresses its content using a linear functional.
+ *
+ * @param colIndices The Column indexes for the column group.
+ * @param coefficents 2D-Array where coefficients[0] is the list of intercepts and coefficients[1] the list of slopes.
+ * @param numRows Number of rows encoded within this column group.
+ */
+ private ColGroupLinearFunctional(int[] colIndices, double[][] coefficents, int numRows) {
+ super(colIndices);
+ this._coefficents = coefficents;
+ this._numRows = numRows;
+ }
+
+ /**
+ * Generate a linear functional column group.
+ *
+ * @param colIndices The specific column indexes that is contained in this column group.
+ * @param coefficents 2D-Array where coefficients[0] is the list of intercepts and coefficients[1] the list of slopes.
+ * @param numRows Number of rows encoded within this column group.
+ * @return A LinearFunctional column group.
+ */
+ public static AColGroup create(int[] colIndices, double[][] coefficents, int numRows) {
+ if(coefficents.length != 2 || colIndices.length != coefficents[0].length)
+ throw new DMLCompressionException("Invalid size of values compared to columns");
+ return new ColGroupLinearFunctional(colIndices, coefficents, numRows);
+ }
+
+
+ @Override
+ protected void computeRowMxx(double[] c, Builtin builtin, int rl, int ru, double[] preAgg) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public CompressionType getCompType() {
+ return CompressionType.LinearFunctional;
+ }
+
+ @Override
+ public ColGroupType getColGroupType() {
+ return ColGroupType.LinearFunctional;
+ }
+
+ @Override
+ public double getMin() {
+ double min = Double.POSITIVE_INFINITY;
+
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ if(slope >= 0 && (intercept + slope) < min) {
+ min = intercept + slope;
+ }
+ else if(slope < 0 && (intercept + _numRows * slope) < min) {
+ min = intercept + _numRows * slope;
+ }
+ }
+
+ return min;
+ }
+
+ @Override
+ public double getMax() {
+ double max = Double.NEGATIVE_INFINITY;
+
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ if(slope >= 0 && (intercept + _numRows * slope) > max) {
+ max = intercept + _numRows * slope;
+ }
+ else if(slope < 0 && (intercept + slope) > max) {
+ max = intercept + slope;
+ }
+ }
+
+ return max;
+ }
+
+ @Override
+ public void decompressToDenseBlock(DenseBlock db, int rl, int ru, int offR, int offC) {
+ int offT = rl + offR;
+ final int nCol = _colIndexes.length;
+ int offS = rl * nCol;
+ for(int row = rl; row < ru; row++, offT++, offS += nCol) {
+ final double[] c = db.values(offT);
+ final int off = db.pos(offT) + offC;
+ for(int j = 0; j < nCol; j++)
+ c[off + _colIndexes[j]] += getIdx(row, j);
+ }
+ }
+
+ @Override
+ public void decompressToSparseBlock(SparseBlock ret, int rl, int ru, int offR, int offC) {
+ final int nCol = _colIndexes.length;
+ for(int i = rl, offT = rl + offR; i < ru; i++, offT++) {
+ for(int j = 0; j < nCol; j++)
+ ret.append(offT, _colIndexes[j] + offC, getIdx(i, j));
+ }
+ }
+
+ @Override
+ public double getIdx(int r, int colIdx) {
+ return _coefficents[0][colIdx] + _coefficents[1][colIdx] * (r + 1);
+ }
+
+ @Override
+ public AColGroup scalarOperation(ScalarOperator op) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup unaryOperation(UnaryOperator op) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup binaryRowOpLeft(BinaryOperator op, double[] v, boolean isRowSafe) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup binaryRowOpRight(BinaryOperator op, double[] v, boolean isRowSafe) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected double computeMxx(double c, Builtin builtin) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected void computeColMxx(double[] c, Builtin builtin) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected void computeSum(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[0] += nRows * (intercept + (nRows + 1) * slope / 2);
+ }
+ }
+
+ @Override
+ public void computeColSums(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[_colIndexes[col]] += nRows * (intercept + (nRows + 1) * slope / 2);
+ }
+ }
+
+ @Override
+ protected void computeSumSq(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[0] += nRows * (Math.pow(intercept, 2) + (nRows + 1) * slope * intercept +
+ (nRows + 1) * (2 * nRows + 1) * Math.pow(slope, 2) / 6);
+ }
+ }
+
+ @Override
+ protected void computeColSumsSq(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[_colIndexes[col]] += nRows * (Math.pow(intercept, 2) + (nRows + 1) * slope * intercept +
+ (nRows + 1) * (2 * nRows + 1) * Math.pow(slope, 2) / 6);
+ }
+ }
+
+ @Override
+ protected void computeRowSums(double[] c, int rl, int ru, double[] preAgg) {
+ double intercept_sum = 0;
+ for(double intercept : _coefficents[0])
+ intercept_sum += intercept;
+
+ double slope_sum = 0;
+ for(double slope : _coefficents[1])
+ slope_sum += slope;
+
+ for(int rix = rl; rix < ru; rix++)
+ c[rix] += intercept_sum + slope_sum * (rix + 1);
+ }
+
+ @Override
+ public int getNumValues() {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup rightMultByMatrix(MatrixBlock right) {
+ final int nColR = right.getNumColumns();
+ final int[] outputCols = Util.genColsIndices(nColR);
+
+ MatrixBlock result = new MatrixBlock(_numRows, nColR, false);
+ for(int j = 0; j < nColR; j++) {
+ double bias_accum = 0.0;
+ double slope_accum = 0.0;
+
+ for(int c = 0; c < _colIndexes.length; c++) {
+ bias_accum += right.getValue(_colIndexes[c], j) * _coefficents[0][c];
+ slope_accum += right.getValue(_colIndexes[c], j) * _coefficents[1][c];
+ }
+
+ for(int r = 0; r < _numRows; r++) {
+ result.setValue(r, j, bias_accum + (r+1) * slope_accum);
+ }
+ }
+
+ // returns an uncompressed ColGroup
+ return ColGroupUncompressed.create(result, outputCols);
+ }
+
+ @Override
+ public void tsmm(double[] ret, int numColumns, int nRows) {
+ // runs in O(tCol^2) since dot-products take O(1) time to compute when both vectors are linearly compressed
+ final int tCol = _colIndexes.length;
+
+ final double sumIndices = nRows * (nRows + 1)/2.0;
+ final double sumSquaredIndices = nRows * (nRows + 1) * (2*nRows + 1)/6.0;
+ for(int row = 0, offTmp = 0; row < tCol; row++, offTmp += tCol) {
+ final double alpha1 = nRows * _coefficents[0][row] + sumIndices * _coefficents[1][row];
+ final double alpha2 = sumIndices * _coefficents[0][row] + sumSquaredIndices * _coefficents[1][row];
+ final int offRet = _colIndexes[row] * numColumns;
+ for(int col = row; col < tCol; col++) {
+ ret[offRet + _colIndexes[col]] += alpha1 * _coefficents[0][col] + alpha2 * _coefficents[1][col];
+ }
+ }
+ }
+
+ @Override
+ public void leftMultByMatrixNoPreAgg(MatrixBlock matrix, MatrixBlock result, int rl, int ru, int cl, int cu) {
+ throw new DMLCompressionException("This method should never be called");
+ }
+
+ @Override
+ public void leftMultByAColGroup(AColGroup lhs, MatrixBlock result) {
+ if(lhs instanceof ColGroupEmpty) {
+ return;
+ }
+
+ MatrixBlock tmpRet = new MatrixBlock(lhs.getNumCols(), _colIndexes.length, 0);
+
+ if(lhs instanceof ColGroupUncompressed) {
+ ColGroupUncompressed lhsUC = (ColGroupUncompressed) lhs;
+ int numRowsLeft = lhsUC.getData().getNumRows();
+
+ double[] colSumsAndWeightedColSums = new double[2 * lhs.getNumCols()];
+ for(int j = 0, offTmp = 0; j < lhs.getNumCols(); j++, offTmp += 2) {
+ for(int i = 0; i < numRowsLeft; i++) {
+ colSumsAndWeightedColSums[offTmp] += lhs.getIdx(i, j);
+ colSumsAndWeightedColSums[offTmp + 1] += (i+1) * lhs.getIdx(i, j);
+ }
+ }
+
+ MatrixBlock sumMatrix = new MatrixBlock(lhs.getNumCols(), 2, colSumsAndWeightedColSums);
+ MatrixBlock coefficientMatrix = DataConverter.convertToMatrixBlock(_coefficents);
+
+ LibMatrixMult.matrixMult(sumMatrix, coefficientMatrix, tmpRet);
+ } else if(lhs instanceof ColGroupLinearFunctional) {
+ ColGroupLinearFunctional lhsLF = (ColGroupLinearFunctional) lhs;
+
+ final double sumIndices = _numRows * (_numRows + 1)/2.0;
+ final double sumSquaredIndices = _numRows * (_numRows + 1) * (2*_numRows + 1)/6.0;
+
+ MatrixBlock weightMatrix = new MatrixBlock(2, 2, new double[] {_numRows, sumIndices, sumIndices, sumSquaredIndices});
+ MatrixBlock coefficientMatrixLhs = DataConverter.convertToMatrixBlock(lhsLF._coefficents);
+ MatrixBlock coefficientMatrixRhs = DataConverter.convertToMatrixBlock(_coefficents);
+
+ coefficientMatrixLhs = LibMatrixReorg.transposeInPlace(coefficientMatrixLhs,
+ InfrastructureAnalyzer.getLocalParallelism());
+
+ // We simply compute a matrix multiplication chain in coefficient space, i.e.,
+ // t(L) %*% R = t(coeff(L)) %*% W %*% coeff(R)
+ // where W is a weight matrix capturing the size of the shared dimension (weightMatrix above)
+ // and coeff(X) denotes the 2 x n matrix of the m x n matrix X.
+ MatrixBlock tmp = new MatrixBlock(lhs.getNumCols(), 2, false);
+ LibMatrixMult.matrixMult(coefficientMatrixLhs, weightMatrix, tmp);
+ LibMatrixMult.matrixMult(tmp, coefficientMatrixRhs, tmpRet);
+ } else if(lhs instanceof APreAgg) {
+ // TODO: implement
+ throw new NotImplementedException();
Review Comment:
i think the best design for this would be some kind of iterator for the functional group that gives double[] line by line that can then be aggregated.
You do not need (i suggest not to) to implement this now
##########
src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupLinearFunctional.java:
##########
@@ -0,0 +1,516 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.sysds.runtime.compress.colgroup;
+
+import org.apache.commons.lang.NotImplementedException;
+import org.apache.sysds.runtime.compress.DMLCompressionException;
+import org.apache.sysds.runtime.compress.cost.ComputationCostEstimator;
+import org.apache.sysds.runtime.compress.utils.Util;
+import org.apache.sysds.runtime.controlprogram.parfor.stat.InfrastructureAnalyzer;
+import org.apache.sysds.runtime.data.DenseBlock;
+import org.apache.sysds.runtime.data.SparseBlock;
+import org.apache.sysds.runtime.functionobjects.Builtin;
+import org.apache.sysds.runtime.instructions.cp.CM_COV_Object;
+import org.apache.sysds.runtime.matrix.data.LibMatrixMult;
+import org.apache.sysds.runtime.matrix.data.LibMatrixReorg;
+import org.apache.sysds.runtime.matrix.data.MatrixBlock;
+import org.apache.sysds.runtime.matrix.operators.BinaryOperator;
+import org.apache.sysds.runtime.matrix.operators.CMOperator;
+import org.apache.sysds.runtime.matrix.operators.ScalarOperator;
+import org.apache.sysds.runtime.matrix.operators.UnaryOperator;
+import org.apache.sysds.runtime.util.DataConverter;
+
+import java.io.DataInput;
+import java.io.DataOutput;
+import java.io.IOException;
+import java.util.Arrays;
+
+public class ColGroupLinearFunctional extends AColGroupCompressed {
+
+ private static final long serialVersionUID = -2811822570758221975L;
+
+ protected double[][] _coefficents;
+
+ protected int _numRows;
+
+ /** Constructor for serialization */
+ protected ColGroupLinearFunctional() {
+ super();
+ }
+
+ /**
+ * Constructs a Linear Functional Column Group that compresses its content using a linear functional.
+ *
+ * @param colIndices The Column indexes for the column group.
+ * @param coefficents 2D-Array where coefficients[0] is the list of intercepts and coefficients[1] the list of slopes.
+ * @param numRows Number of rows encoded within this column group.
+ */
+ private ColGroupLinearFunctional(int[] colIndices, double[][] coefficents, int numRows) {
+ super(colIndices);
+ this._coefficents = coefficents;
+ this._numRows = numRows;
+ }
+
+ /**
+ * Generate a linear functional column group.
+ *
+ * @param colIndices The specific column indexes that is contained in this column group.
+ * @param coefficents 2D-Array where coefficients[0] is the list of intercepts and coefficients[1] the list of slopes.
+ * @param numRows Number of rows encoded within this column group.
+ * @return A LinearFunctional column group.
+ */
+ public static AColGroup create(int[] colIndices, double[][] coefficents, int numRows) {
+ if(coefficents.length != 2 || colIndices.length != coefficents[0].length)
+ throw new DMLCompressionException("Invalid size of values compared to columns");
+ return new ColGroupLinearFunctional(colIndices, coefficents, numRows);
+ }
+
+
+ @Override
+ protected void computeRowMxx(double[] c, Builtin builtin, int rl, int ru, double[] preAgg) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public CompressionType getCompType() {
+ return CompressionType.LinearFunctional;
+ }
+
+ @Override
+ public ColGroupType getColGroupType() {
+ return ColGroupType.LinearFunctional;
+ }
+
+ @Override
+ public double getMin() {
+ double min = Double.POSITIVE_INFINITY;
+
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ if(slope >= 0 && (intercept + slope) < min) {
+ min = intercept + slope;
+ }
+ else if(slope < 0 && (intercept + _numRows * slope) < min) {
+ min = intercept + _numRows * slope;
+ }
+ }
+
+ return min;
+ }
+
+ @Override
+ public double getMax() {
+ double max = Double.NEGATIVE_INFINITY;
+
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ if(slope >= 0 && (intercept + _numRows * slope) > max) {
+ max = intercept + _numRows * slope;
+ }
+ else if(slope < 0 && (intercept + slope) > max) {
+ max = intercept + slope;
+ }
+ }
+
+ return max;
+ }
+
+ @Override
+ public void decompressToDenseBlock(DenseBlock db, int rl, int ru, int offR, int offC) {
+ int offT = rl + offR;
+ final int nCol = _colIndexes.length;
+ int offS = rl * nCol;
+ for(int row = rl; row < ru; row++, offT++, offS += nCol) {
+ final double[] c = db.values(offT);
+ final int off = db.pos(offT) + offC;
+ for(int j = 0; j < nCol; j++)
+ c[off + _colIndexes[j]] += getIdx(row, j);
+ }
+ }
+
+ @Override
+ public void decompressToSparseBlock(SparseBlock ret, int rl, int ru, int offR, int offC) {
+ final int nCol = _colIndexes.length;
+ for(int i = rl, offT = rl + offR; i < ru; i++, offT++) {
+ for(int j = 0; j < nCol; j++)
+ ret.append(offT, _colIndexes[j] + offC, getIdx(i, j));
+ }
+ }
+
+ @Override
+ public double getIdx(int r, int colIdx) {
+ return _coefficents[0][colIdx] + _coefficents[1][colIdx] * (r + 1);
+ }
+
+ @Override
+ public AColGroup scalarOperation(ScalarOperator op) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup unaryOperation(UnaryOperator op) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup binaryRowOpLeft(BinaryOperator op, double[] v, boolean isRowSafe) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup binaryRowOpRight(BinaryOperator op, double[] v, boolean isRowSafe) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected double computeMxx(double c, Builtin builtin) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected void computeColMxx(double[] c, Builtin builtin) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected void computeSum(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[0] += nRows * (intercept + (nRows + 1) * slope / 2);
+ }
+ }
+
+ @Override
+ public void computeColSums(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[_colIndexes[col]] += nRows * (intercept + (nRows + 1) * slope / 2);
+ }
+ }
+
+ @Override
+ protected void computeSumSq(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[0] += nRows * (Math.pow(intercept, 2) + (nRows + 1) * slope * intercept +
+ (nRows + 1) * (2 * nRows + 1) * Math.pow(slope, 2) / 6);
+ }
+ }
+
+ @Override
+ protected void computeColSumsSq(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[_colIndexes[col]] += nRows * (Math.pow(intercept, 2) + (nRows + 1) * slope * intercept +
+ (nRows + 1) * (2 * nRows + 1) * Math.pow(slope, 2) / 6);
+ }
+ }
+
+ @Override
+ protected void computeRowSums(double[] c, int rl, int ru, double[] preAgg) {
+ double intercept_sum = 0;
+ for(double intercept : _coefficents[0])
+ intercept_sum += intercept;
+
+ double slope_sum = 0;
+ for(double slope : _coefficents[1])
+ slope_sum += slope;
+
+ for(int rix = rl; rix < ru; rix++)
+ c[rix] += intercept_sum + slope_sum * (rix + 1);
+ }
+
+ @Override
+ public int getNumValues() {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup rightMultByMatrix(MatrixBlock right) {
+ final int nColR = right.getNumColumns();
+ final int[] outputCols = Util.genColsIndices(nColR);
+
+ MatrixBlock result = new MatrixBlock(_numRows, nColR, false);
+ for(int j = 0; j < nColR; j++) {
Review Comment:
add a TODO for specialization with sparse and dense matrix block
##########
src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupLinearFunctional.java:
##########
@@ -0,0 +1,516 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.sysds.runtime.compress.colgroup;
+
+import org.apache.commons.lang.NotImplementedException;
+import org.apache.sysds.runtime.compress.DMLCompressionException;
+import org.apache.sysds.runtime.compress.cost.ComputationCostEstimator;
+import org.apache.sysds.runtime.compress.utils.Util;
+import org.apache.sysds.runtime.controlprogram.parfor.stat.InfrastructureAnalyzer;
+import org.apache.sysds.runtime.data.DenseBlock;
+import org.apache.sysds.runtime.data.SparseBlock;
+import org.apache.sysds.runtime.functionobjects.Builtin;
+import org.apache.sysds.runtime.instructions.cp.CM_COV_Object;
+import org.apache.sysds.runtime.matrix.data.LibMatrixMult;
+import org.apache.sysds.runtime.matrix.data.LibMatrixReorg;
+import org.apache.sysds.runtime.matrix.data.MatrixBlock;
+import org.apache.sysds.runtime.matrix.operators.BinaryOperator;
+import org.apache.sysds.runtime.matrix.operators.CMOperator;
+import org.apache.sysds.runtime.matrix.operators.ScalarOperator;
+import org.apache.sysds.runtime.matrix.operators.UnaryOperator;
+import org.apache.sysds.runtime.util.DataConverter;
+
+import java.io.DataInput;
+import java.io.DataOutput;
+import java.io.IOException;
+import java.util.Arrays;
+
+public class ColGroupLinearFunctional extends AColGroupCompressed {
+
+ private static final long serialVersionUID = -2811822570758221975L;
+
+ protected double[][] _coefficents;
+
+ protected int _numRows;
+
+ /** Constructor for serialization */
+ protected ColGroupLinearFunctional() {
+ super();
+ }
+
+ /**
+ * Constructs a Linear Functional Column Group that compresses its content using a linear functional.
+ *
+ * @param colIndices The Column indexes for the column group.
+ * @param coefficents 2D-Array where coefficients[0] is the list of intercepts and coefficients[1] the list of slopes.
+ * @param numRows Number of rows encoded within this column group.
+ */
+ private ColGroupLinearFunctional(int[] colIndices, double[][] coefficents, int numRows) {
+ super(colIndices);
+ this._coefficents = coefficents;
+ this._numRows = numRows;
+ }
+
+ /**
+ * Generate a linear functional column group.
+ *
+ * @param colIndices The specific column indexes that is contained in this column group.
+ * @param coefficents 2D-Array where coefficients[0] is the list of intercepts and coefficients[1] the list of slopes.
+ * @param numRows Number of rows encoded within this column group.
+ * @return A LinearFunctional column group.
+ */
+ public static AColGroup create(int[] colIndices, double[][] coefficents, int numRows) {
+ if(coefficents.length != 2 || colIndices.length != coefficents[0].length)
+ throw new DMLCompressionException("Invalid size of values compared to columns");
+ return new ColGroupLinearFunctional(colIndices, coefficents, numRows);
+ }
+
+
+ @Override
+ protected void computeRowMxx(double[] c, Builtin builtin, int rl, int ru, double[] preAgg) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public CompressionType getCompType() {
+ return CompressionType.LinearFunctional;
+ }
+
+ @Override
+ public ColGroupType getColGroupType() {
+ return ColGroupType.LinearFunctional;
+ }
+
+ @Override
+ public double getMin() {
+ double min = Double.POSITIVE_INFINITY;
+
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ if(slope >= 0 && (intercept + slope) < min) {
+ min = intercept + slope;
+ }
+ else if(slope < 0 && (intercept + _numRows * slope) < min) {
+ min = intercept + _numRows * slope;
+ }
+ }
+
+ return min;
+ }
+
+ @Override
+ public double getMax() {
+ double max = Double.NEGATIVE_INFINITY;
+
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ if(slope >= 0 && (intercept + _numRows * slope) > max) {
+ max = intercept + _numRows * slope;
+ }
+ else if(slope < 0 && (intercept + slope) > max) {
+ max = intercept + slope;
+ }
+ }
+
+ return max;
+ }
+
+ @Override
+ public void decompressToDenseBlock(DenseBlock db, int rl, int ru, int offR, int offC) {
+ int offT = rl + offR;
+ final int nCol = _colIndexes.length;
+ int offS = rl * nCol;
+ for(int row = rl; row < ru; row++, offT++, offS += nCol) {
+ final double[] c = db.values(offT);
+ final int off = db.pos(offT) + offC;
+ for(int j = 0; j < nCol; j++)
+ c[off + _colIndexes[j]] += getIdx(row, j);
+ }
+ }
+
+ @Override
+ public void decompressToSparseBlock(SparseBlock ret, int rl, int ru, int offR, int offC) {
+ final int nCol = _colIndexes.length;
+ for(int i = rl, offT = rl + offR; i < ru; i++, offT++) {
+ for(int j = 0; j < nCol; j++)
+ ret.append(offT, _colIndexes[j] + offC, getIdx(i, j));
+ }
+ }
+
+ @Override
+ public double getIdx(int r, int colIdx) {
+ return _coefficents[0][colIdx] + _coefficents[1][colIdx] * (r + 1);
+ }
+
+ @Override
+ public AColGroup scalarOperation(ScalarOperator op) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup unaryOperation(UnaryOperator op) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup binaryRowOpLeft(BinaryOperator op, double[] v, boolean isRowSafe) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup binaryRowOpRight(BinaryOperator op, double[] v, boolean isRowSafe) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected double computeMxx(double c, Builtin builtin) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected void computeColMxx(double[] c, Builtin builtin) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected void computeSum(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[0] += nRows * (intercept + (nRows + 1) * slope / 2);
+ }
+ }
+
+ @Override
+ public void computeColSums(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[_colIndexes[col]] += nRows * (intercept + (nRows + 1) * slope / 2);
+ }
+ }
+
+ @Override
+ protected void computeSumSq(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[0] += nRows * (Math.pow(intercept, 2) + (nRows + 1) * slope * intercept +
+ (nRows + 1) * (2 * nRows + 1) * Math.pow(slope, 2) / 6);
+ }
+ }
+
+ @Override
+ protected void computeColSumsSq(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[_colIndexes[col]] += nRows * (Math.pow(intercept, 2) + (nRows + 1) * slope * intercept +
+ (nRows + 1) * (2 * nRows + 1) * Math.pow(slope, 2) / 6);
+ }
+ }
+
+ @Override
+ protected void computeRowSums(double[] c, int rl, int ru, double[] preAgg) {
+ double intercept_sum = 0;
+ for(double intercept : _coefficents[0])
+ intercept_sum += intercept;
+
+ double slope_sum = 0;
+ for(double slope : _coefficents[1])
+ slope_sum += slope;
+
+ for(int rix = rl; rix < ru; rix++)
+ c[rix] += intercept_sum + slope_sum * (rix + 1);
+ }
+
+ @Override
+ public int getNumValues() {
+ throw new NotImplementedException();
Review Comment:
return 0;
##########
src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupLinearFunctional.java:
##########
@@ -0,0 +1,516 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.sysds.runtime.compress.colgroup;
+
+import org.apache.commons.lang.NotImplementedException;
+import org.apache.sysds.runtime.compress.DMLCompressionException;
+import org.apache.sysds.runtime.compress.cost.ComputationCostEstimator;
+import org.apache.sysds.runtime.compress.utils.Util;
+import org.apache.sysds.runtime.controlprogram.parfor.stat.InfrastructureAnalyzer;
+import org.apache.sysds.runtime.data.DenseBlock;
+import org.apache.sysds.runtime.data.SparseBlock;
+import org.apache.sysds.runtime.functionobjects.Builtin;
+import org.apache.sysds.runtime.instructions.cp.CM_COV_Object;
+import org.apache.sysds.runtime.matrix.data.LibMatrixMult;
+import org.apache.sysds.runtime.matrix.data.LibMatrixReorg;
+import org.apache.sysds.runtime.matrix.data.MatrixBlock;
+import org.apache.sysds.runtime.matrix.operators.BinaryOperator;
+import org.apache.sysds.runtime.matrix.operators.CMOperator;
+import org.apache.sysds.runtime.matrix.operators.ScalarOperator;
+import org.apache.sysds.runtime.matrix.operators.UnaryOperator;
+import org.apache.sysds.runtime.util.DataConverter;
+
+import java.io.DataInput;
+import java.io.DataOutput;
+import java.io.IOException;
+import java.util.Arrays;
+
+public class ColGroupLinearFunctional extends AColGroupCompressed {
+
+ private static final long serialVersionUID = -2811822570758221975L;
+
+ protected double[][] _coefficents;
+
+ protected int _numRows;
+
+ /** Constructor for serialization */
+ protected ColGroupLinearFunctional() {
+ super();
+ }
+
+ /**
+ * Constructs a Linear Functional Column Group that compresses its content using a linear functional.
+ *
+ * @param colIndices The Column indexes for the column group.
+ * @param coefficents 2D-Array where coefficients[0] is the list of intercepts and coefficients[1] the list of slopes.
+ * @param numRows Number of rows encoded within this column group.
+ */
+ private ColGroupLinearFunctional(int[] colIndices, double[][] coefficents, int numRows) {
+ super(colIndices);
+ this._coefficents = coefficents;
+ this._numRows = numRows;
+ }
+
+ /**
+ * Generate a linear functional column group.
+ *
+ * @param colIndices The specific column indexes that is contained in this column group.
+ * @param coefficents 2D-Array where coefficients[0] is the list of intercepts and coefficients[1] the list of slopes.
+ * @param numRows Number of rows encoded within this column group.
+ * @return A LinearFunctional column group.
+ */
+ public static AColGroup create(int[] colIndices, double[][] coefficents, int numRows) {
+ if(coefficents.length != 2 || colIndices.length != coefficents[0].length)
+ throw new DMLCompressionException("Invalid size of values compared to columns");
+ return new ColGroupLinearFunctional(colIndices, coefficents, numRows);
+ }
+
+
+ @Override
+ protected void computeRowMxx(double[] c, Builtin builtin, int rl, int ru, double[] preAgg) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public CompressionType getCompType() {
+ return CompressionType.LinearFunctional;
+ }
+
+ @Override
+ public ColGroupType getColGroupType() {
+ return ColGroupType.LinearFunctional;
+ }
+
+ @Override
+ public double getMin() {
+ double min = Double.POSITIVE_INFINITY;
+
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ if(slope >= 0 && (intercept + slope) < min) {
+ min = intercept + slope;
+ }
+ else if(slope < 0 && (intercept + _numRows * slope) < min) {
+ min = intercept + _numRows * slope;
+ }
+ }
+
+ return min;
+ }
+
+ @Override
+ public double getMax() {
+ double max = Double.NEGATIVE_INFINITY;
+
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ if(slope >= 0 && (intercept + _numRows * slope) > max) {
+ max = intercept + _numRows * slope;
+ }
+ else if(slope < 0 && (intercept + slope) > max) {
+ max = intercept + slope;
+ }
+ }
+
+ return max;
+ }
+
+ @Override
+ public void decompressToDenseBlock(DenseBlock db, int rl, int ru, int offR, int offC) {
+ int offT = rl + offR;
+ final int nCol = _colIndexes.length;
+ int offS = rl * nCol;
+ for(int row = rl; row < ru; row++, offT++, offS += nCol) {
+ final double[] c = db.values(offT);
+ final int off = db.pos(offT) + offC;
+ for(int j = 0; j < nCol; j++)
+ c[off + _colIndexes[j]] += getIdx(row, j);
+ }
+ }
+
+ @Override
+ public void decompressToSparseBlock(SparseBlock ret, int rl, int ru, int offR, int offC) {
+ final int nCol = _colIndexes.length;
+ for(int i = rl, offT = rl + offR; i < ru; i++, offT++) {
+ for(int j = 0; j < nCol; j++)
+ ret.append(offT, _colIndexes[j] + offC, getIdx(i, j));
+ }
+ }
+
+ @Override
+ public double getIdx(int r, int colIdx) {
+ return _coefficents[0][colIdx] + _coefficents[1][colIdx] * (r + 1);
+ }
+
+ @Override
+ public AColGroup scalarOperation(ScalarOperator op) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup unaryOperation(UnaryOperator op) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup binaryRowOpLeft(BinaryOperator op, double[] v, boolean isRowSafe) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup binaryRowOpRight(BinaryOperator op, double[] v, boolean isRowSafe) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected double computeMxx(double c, Builtin builtin) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected void computeColMxx(double[] c, Builtin builtin) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected void computeSum(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[0] += nRows * (intercept + (nRows + 1) * slope / 2);
+ }
+ }
+
+ @Override
+ public void computeColSums(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[_colIndexes[col]] += nRows * (intercept + (nRows + 1) * slope / 2);
+ }
+ }
+
+ @Override
+ protected void computeSumSq(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[0] += nRows * (Math.pow(intercept, 2) + (nRows + 1) * slope * intercept +
+ (nRows + 1) * (2 * nRows + 1) * Math.pow(slope, 2) / 6);
+ }
+ }
+
+ @Override
+ protected void computeColSumsSq(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[_colIndexes[col]] += nRows * (Math.pow(intercept, 2) + (nRows + 1) * slope * intercept +
+ (nRows + 1) * (2 * nRows + 1) * Math.pow(slope, 2) / 6);
+ }
+ }
+
+ @Override
+ protected void computeRowSums(double[] c, int rl, int ru, double[] preAgg) {
+ double intercept_sum = 0;
+ for(double intercept : _coefficents[0])
+ intercept_sum += intercept;
+
+ double slope_sum = 0;
+ for(double slope : _coefficents[1])
+ slope_sum += slope;
+
+ for(int rix = rl; rix < ru; rix++)
+ c[rix] += intercept_sum + slope_sum * (rix + 1);
+ }
+
+ @Override
+ public int getNumValues() {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup rightMultByMatrix(MatrixBlock right) {
+ final int nColR = right.getNumColumns();
+ final int[] outputCols = Util.genColsIndices(nColR);
+
+ MatrixBlock result = new MatrixBlock(_numRows, nColR, false);
+ for(int j = 0; j < nColR; j++) {
+ double bias_accum = 0.0;
+ double slope_accum = 0.0;
+
+ for(int c = 0; c < _colIndexes.length; c++) {
+ bias_accum += right.getValue(_colIndexes[c], j) * _coefficents[0][c];
+ slope_accum += right.getValue(_colIndexes[c], j) * _coefficents[1][c];
+ }
+
+ for(int r = 0; r < _numRows; r++) {
+ result.setValue(r, j, bias_accum + (r+1) * slope_accum);
+ }
+ }
+
+ // returns an uncompressed ColGroup
+ return ColGroupUncompressed.create(result, outputCols);
+ }
+
+ @Override
+ public void tsmm(double[] ret, int numColumns, int nRows) {
+ // runs in O(tCol^2) since dot-products take O(1) time to compute when both vectors are linearly compressed
+ final int tCol = _colIndexes.length;
+
+ final double sumIndices = nRows * (nRows + 1)/2.0;
+ final double sumSquaredIndices = nRows * (nRows + 1) * (2*nRows + 1)/6.0;
+ for(int row = 0, offTmp = 0; row < tCol; row++, offTmp += tCol) {
+ final double alpha1 = nRows * _coefficents[0][row] + sumIndices * _coefficents[1][row];
+ final double alpha2 = sumIndices * _coefficents[0][row] + sumSquaredIndices * _coefficents[1][row];
+ final int offRet = _colIndexes[row] * numColumns;
+ for(int col = row; col < tCol; col++) {
+ ret[offRet + _colIndexes[col]] += alpha1 * _coefficents[0][col] + alpha2 * _coefficents[1][col];
+ }
+ }
+ }
+
+ @Override
+ public void leftMultByMatrixNoPreAgg(MatrixBlock matrix, MatrixBlock result, int rl, int ru, int cl, int cu) {
+ throw new DMLCompressionException("This method should never be called");
+ }
+
+ @Override
+ public void leftMultByAColGroup(AColGroup lhs, MatrixBlock result) {
+ if(lhs instanceof ColGroupEmpty) {
+ return;
+ }
+
+ MatrixBlock tmpRet = new MatrixBlock(lhs.getNumCols(), _colIndexes.length, 0);
+
+ if(lhs instanceof ColGroupUncompressed) {
+ ColGroupUncompressed lhsUC = (ColGroupUncompressed) lhs;
+ int numRowsLeft = lhsUC.getData().getNumRows();
+
+ double[] colSumsAndWeightedColSums = new double[2 * lhs.getNumCols()];
+ for(int j = 0, offTmp = 0; j < lhs.getNumCols(); j++, offTmp += 2) {
+ for(int i = 0; i < numRowsLeft; i++) {
+ colSumsAndWeightedColSums[offTmp] += lhs.getIdx(i, j);
+ colSumsAndWeightedColSums[offTmp + 1] += (i+1) * lhs.getIdx(i, j);
+ }
+ }
+
+ MatrixBlock sumMatrix = new MatrixBlock(lhs.getNumCols(), 2, colSumsAndWeightedColSums);
+ MatrixBlock coefficientMatrix = DataConverter.convertToMatrixBlock(_coefficents);
+
+ LibMatrixMult.matrixMult(sumMatrix, coefficientMatrix, tmpRet);
+ } else if(lhs instanceof ColGroupLinearFunctional) {
+ ColGroupLinearFunctional lhsLF = (ColGroupLinearFunctional) lhs;
+
+ final double sumIndices = _numRows * (_numRows + 1)/2.0;
+ final double sumSquaredIndices = _numRows * (_numRows + 1) * (2*_numRows + 1)/6.0;
+
+ MatrixBlock weightMatrix = new MatrixBlock(2, 2, new double[] {_numRows, sumIndices, sumIndices, sumSquaredIndices});
+ MatrixBlock coefficientMatrixLhs = DataConverter.convertToMatrixBlock(lhsLF._coefficents);
+ MatrixBlock coefficientMatrixRhs = DataConverter.convertToMatrixBlock(_coefficents);
+
+ coefficientMatrixLhs = LibMatrixReorg.transposeInPlace(coefficientMatrixLhs,
+ InfrastructureAnalyzer.getLocalParallelism());
+
+ // We simply compute a matrix multiplication chain in coefficient space, i.e.,
+ // t(L) %*% R = t(coeff(L)) %*% W %*% coeff(R)
+ // where W is a weight matrix capturing the size of the shared dimension (weightMatrix above)
+ // and coeff(X) denotes the 2 x n matrix of the m x n matrix X.
+ MatrixBlock tmp = new MatrixBlock(lhs.getNumCols(), 2, false);
+ LibMatrixMult.matrixMult(coefficientMatrixLhs, weightMatrix, tmp);
+ LibMatrixMult.matrixMult(tmp, coefficientMatrixRhs, tmpRet);
Review Comment:
next level would be to not use a tempRet but instead directly output the result into the output matrix.
##########
src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupLinearFunctional.java:
##########
@@ -0,0 +1,516 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.sysds.runtime.compress.colgroup;
+
+import org.apache.commons.lang.NotImplementedException;
+import org.apache.sysds.runtime.compress.DMLCompressionException;
+import org.apache.sysds.runtime.compress.cost.ComputationCostEstimator;
+import org.apache.sysds.runtime.compress.utils.Util;
+import org.apache.sysds.runtime.controlprogram.parfor.stat.InfrastructureAnalyzer;
+import org.apache.sysds.runtime.data.DenseBlock;
+import org.apache.sysds.runtime.data.SparseBlock;
+import org.apache.sysds.runtime.functionobjects.Builtin;
+import org.apache.sysds.runtime.instructions.cp.CM_COV_Object;
+import org.apache.sysds.runtime.matrix.data.LibMatrixMult;
+import org.apache.sysds.runtime.matrix.data.LibMatrixReorg;
+import org.apache.sysds.runtime.matrix.data.MatrixBlock;
+import org.apache.sysds.runtime.matrix.operators.BinaryOperator;
+import org.apache.sysds.runtime.matrix.operators.CMOperator;
+import org.apache.sysds.runtime.matrix.operators.ScalarOperator;
+import org.apache.sysds.runtime.matrix.operators.UnaryOperator;
+import org.apache.sysds.runtime.util.DataConverter;
+
+import java.io.DataInput;
+import java.io.DataOutput;
+import java.io.IOException;
+import java.util.Arrays;
+
+public class ColGroupLinearFunctional extends AColGroupCompressed {
+
+ private static final long serialVersionUID = -2811822570758221975L;
+
+ protected double[][] _coefficents;
+
+ protected int _numRows;
+
+ /** Constructor for serialization */
+ protected ColGroupLinearFunctional() {
+ super();
+ }
+
+ /**
+ * Constructs a Linear Functional Column Group that compresses its content using a linear functional.
+ *
+ * @param colIndices The Column indexes for the column group.
+ * @param coefficents 2D-Array where coefficients[0] is the list of intercepts and coefficients[1] the list of slopes.
+ * @param numRows Number of rows encoded within this column group.
+ */
+ private ColGroupLinearFunctional(int[] colIndices, double[][] coefficents, int numRows) {
+ super(colIndices);
+ this._coefficents = coefficents;
+ this._numRows = numRows;
+ }
+
+ /**
+ * Generate a linear functional column group.
+ *
+ * @param colIndices The specific column indexes that is contained in this column group.
+ * @param coefficents 2D-Array where coefficients[0] is the list of intercepts and coefficients[1] the list of slopes.
+ * @param numRows Number of rows encoded within this column group.
+ * @return A LinearFunctional column group.
+ */
+ public static AColGroup create(int[] colIndices, double[][] coefficents, int numRows) {
+ if(coefficents.length != 2 || colIndices.length != coefficents[0].length)
+ throw new DMLCompressionException("Invalid size of values compared to columns");
+ return new ColGroupLinearFunctional(colIndices, coefficents, numRows);
+ }
+
+
+ @Override
+ protected void computeRowMxx(double[] c, Builtin builtin, int rl, int ru, double[] preAgg) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public CompressionType getCompType() {
+ return CompressionType.LinearFunctional;
+ }
+
+ @Override
+ public ColGroupType getColGroupType() {
+ return ColGroupType.LinearFunctional;
+ }
+
+ @Override
+ public double getMin() {
+ double min = Double.POSITIVE_INFINITY;
+
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ if(slope >= 0 && (intercept + slope) < min) {
+ min = intercept + slope;
+ }
+ else if(slope < 0 && (intercept + _numRows * slope) < min) {
+ min = intercept + _numRows * slope;
+ }
+ }
+
+ return min;
+ }
+
+ @Override
+ public double getMax() {
+ double max = Double.NEGATIVE_INFINITY;
+
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ if(slope >= 0 && (intercept + _numRows * slope) > max) {
+ max = intercept + _numRows * slope;
+ }
+ else if(slope < 0 && (intercept + slope) > max) {
+ max = intercept + slope;
+ }
+ }
+
+ return max;
+ }
+
+ @Override
+ public void decompressToDenseBlock(DenseBlock db, int rl, int ru, int offR, int offC) {
+ int offT = rl + offR;
+ final int nCol = _colIndexes.length;
+ int offS = rl * nCol;
+ for(int row = rl; row < ru; row++, offT++, offS += nCol) {
+ final double[] c = db.values(offT);
+ final int off = db.pos(offT) + offC;
+ for(int j = 0; j < nCol; j++)
+ c[off + _colIndexes[j]] += getIdx(row, j);
+ }
+ }
+
+ @Override
+ public void decompressToSparseBlock(SparseBlock ret, int rl, int ru, int offR, int offC) {
+ final int nCol = _colIndexes.length;
+ for(int i = rl, offT = rl + offR; i < ru; i++, offT++) {
+ for(int j = 0; j < nCol; j++)
+ ret.append(offT, _colIndexes[j] + offC, getIdx(i, j));
+ }
+ }
+
+ @Override
+ public double getIdx(int r, int colIdx) {
+ return _coefficents[0][colIdx] + _coefficents[1][colIdx] * (r + 1);
+ }
+
+ @Override
+ public AColGroup scalarOperation(ScalarOperator op) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup unaryOperation(UnaryOperator op) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup binaryRowOpLeft(BinaryOperator op, double[] v, boolean isRowSafe) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup binaryRowOpRight(BinaryOperator op, double[] v, boolean isRowSafe) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected double computeMxx(double c, Builtin builtin) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected void computeColMxx(double[] c, Builtin builtin) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected void computeSum(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[0] += nRows * (intercept + (nRows + 1) * slope / 2);
+ }
+ }
+
+ @Override
+ public void computeColSums(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[_colIndexes[col]] += nRows * (intercept + (nRows + 1) * slope / 2);
+ }
+ }
+
+ @Override
+ protected void computeSumSq(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[0] += nRows * (Math.pow(intercept, 2) + (nRows + 1) * slope * intercept +
+ (nRows + 1) * (2 * nRows + 1) * Math.pow(slope, 2) / 6);
+ }
+ }
+
+ @Override
+ protected void computeColSumsSq(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[_colIndexes[col]] += nRows * (Math.pow(intercept, 2) + (nRows + 1) * slope * intercept +
+ (nRows + 1) * (2 * nRows + 1) * Math.pow(slope, 2) / 6);
+ }
+ }
+
+ @Override
+ protected void computeRowSums(double[] c, int rl, int ru, double[] preAgg) {
+ double intercept_sum = 0;
+ for(double intercept : _coefficents[0])
+ intercept_sum += intercept;
+
+ double slope_sum = 0;
+ for(double slope : _coefficents[1])
+ slope_sum += slope;
+
+ for(int rix = rl; rix < ru; rix++)
+ c[rix] += intercept_sum + slope_sum * (rix + 1);
+ }
+
+ @Override
+ public int getNumValues() {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup rightMultByMatrix(MatrixBlock right) {
+ final int nColR = right.getNumColumns();
+ final int[] outputCols = Util.genColsIndices(nColR);
+
+ MatrixBlock result = new MatrixBlock(_numRows, nColR, false);
+ for(int j = 0; j < nColR; j++) {
+ double bias_accum = 0.0;
+ double slope_accum = 0.0;
+
+ for(int c = 0; c < _colIndexes.length; c++) {
+ bias_accum += right.getValue(_colIndexes[c], j) * _coefficents[0][c];
+ slope_accum += right.getValue(_colIndexes[c], j) * _coefficents[1][c];
+ }
+
+ for(int r = 0; r < _numRows; r++) {
+ result.setValue(r, j, bias_accum + (r+1) * slope_accum);
+ }
+ }
+
+ // returns an uncompressed ColGroup
+ return ColGroupUncompressed.create(result, outputCols);
Review Comment:
aw, this is sad to return a uncompressed matrix, but i understand the reasons.
##########
src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupLinearFunctional.java:
##########
@@ -0,0 +1,516 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.sysds.runtime.compress.colgroup;
+
+import org.apache.commons.lang.NotImplementedException;
+import org.apache.sysds.runtime.compress.DMLCompressionException;
+import org.apache.sysds.runtime.compress.cost.ComputationCostEstimator;
+import org.apache.sysds.runtime.compress.utils.Util;
+import org.apache.sysds.runtime.controlprogram.parfor.stat.InfrastructureAnalyzer;
+import org.apache.sysds.runtime.data.DenseBlock;
+import org.apache.sysds.runtime.data.SparseBlock;
+import org.apache.sysds.runtime.functionobjects.Builtin;
+import org.apache.sysds.runtime.instructions.cp.CM_COV_Object;
+import org.apache.sysds.runtime.matrix.data.LibMatrixMult;
+import org.apache.sysds.runtime.matrix.data.LibMatrixReorg;
+import org.apache.sysds.runtime.matrix.data.MatrixBlock;
+import org.apache.sysds.runtime.matrix.operators.BinaryOperator;
+import org.apache.sysds.runtime.matrix.operators.CMOperator;
+import org.apache.sysds.runtime.matrix.operators.ScalarOperator;
+import org.apache.sysds.runtime.matrix.operators.UnaryOperator;
+import org.apache.sysds.runtime.util.DataConverter;
+
+import java.io.DataInput;
+import java.io.DataOutput;
+import java.io.IOException;
+import java.util.Arrays;
+
+public class ColGroupLinearFunctional extends AColGroupCompressed {
+
+ private static final long serialVersionUID = -2811822570758221975L;
+
+ protected double[][] _coefficents;
+
+ protected int _numRows;
+
+ /** Constructor for serialization */
+ protected ColGroupLinearFunctional() {
+ super();
+ }
+
+ /**
+ * Constructs a Linear Functional Column Group that compresses its content using a linear functional.
+ *
+ * @param colIndices The Column indexes for the column group.
+ * @param coefficents 2D-Array where coefficients[0] is the list of intercepts and coefficients[1] the list of slopes.
+ * @param numRows Number of rows encoded within this column group.
+ */
+ private ColGroupLinearFunctional(int[] colIndices, double[][] coefficents, int numRows) {
+ super(colIndices);
+ this._coefficents = coefficents;
+ this._numRows = numRows;
+ }
+
+ /**
+ * Generate a linear functional column group.
+ *
+ * @param colIndices The specific column indexes that is contained in this column group.
+ * @param coefficents 2D-Array where coefficients[0] is the list of intercepts and coefficients[1] the list of slopes.
+ * @param numRows Number of rows encoded within this column group.
+ * @return A LinearFunctional column group.
+ */
+ public static AColGroup create(int[] colIndices, double[][] coefficents, int numRows) {
+ if(coefficents.length != 2 || colIndices.length != coefficents[0].length)
+ throw new DMLCompressionException("Invalid size of values compared to columns");
+ return new ColGroupLinearFunctional(colIndices, coefficents, numRows);
+ }
+
+
+ @Override
+ protected void computeRowMxx(double[] c, Builtin builtin, int rl, int ru, double[] preAgg) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public CompressionType getCompType() {
+ return CompressionType.LinearFunctional;
+ }
+
+ @Override
+ public ColGroupType getColGroupType() {
+ return ColGroupType.LinearFunctional;
+ }
+
+ @Override
+ public double getMin() {
+ double min = Double.POSITIVE_INFINITY;
+
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ if(slope >= 0 && (intercept + slope) < min) {
+ min = intercept + slope;
+ }
+ else if(slope < 0 && (intercept + _numRows * slope) < min) {
+ min = intercept + _numRows * slope;
+ }
+ }
+
+ return min;
+ }
+
+ @Override
+ public double getMax() {
+ double max = Double.NEGATIVE_INFINITY;
+
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ if(slope >= 0 && (intercept + _numRows * slope) > max) {
+ max = intercept + _numRows * slope;
+ }
+ else if(slope < 0 && (intercept + slope) > max) {
+ max = intercept + slope;
+ }
+ }
+
+ return max;
+ }
+
+ @Override
+ public void decompressToDenseBlock(DenseBlock db, int rl, int ru, int offR, int offC) {
+ int offT = rl + offR;
+ final int nCol = _colIndexes.length;
+ int offS = rl * nCol;
+ for(int row = rl; row < ru; row++, offT++, offS += nCol) {
+ final double[] c = db.values(offT);
+ final int off = db.pos(offT) + offC;
+ for(int j = 0; j < nCol; j++)
+ c[off + _colIndexes[j]] += getIdx(row, j);
+ }
+ }
+
+ @Override
+ public void decompressToSparseBlock(SparseBlock ret, int rl, int ru, int offR, int offC) {
+ final int nCol = _colIndexes.length;
+ for(int i = rl, offT = rl + offR; i < ru; i++, offT++) {
+ for(int j = 0; j < nCol; j++)
+ ret.append(offT, _colIndexes[j] + offC, getIdx(i, j));
+ }
+ }
+
+ @Override
+ public double getIdx(int r, int colIdx) {
+ return _coefficents[0][colIdx] + _coefficents[1][colIdx] * (r + 1);
+ }
+
+ @Override
+ public AColGroup scalarOperation(ScalarOperator op) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup unaryOperation(UnaryOperator op) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup binaryRowOpLeft(BinaryOperator op, double[] v, boolean isRowSafe) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup binaryRowOpRight(BinaryOperator op, double[] v, boolean isRowSafe) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected double computeMxx(double c, Builtin builtin) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected void computeColMxx(double[] c, Builtin builtin) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected void computeSum(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[0] += nRows * (intercept + (nRows + 1) * slope / 2);
+ }
+ }
+
+ @Override
+ public void computeColSums(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[_colIndexes[col]] += nRows * (intercept + (nRows + 1) * slope / 2);
+ }
+ }
+
+ @Override
+ protected void computeSumSq(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[0] += nRows * (Math.pow(intercept, 2) + (nRows + 1) * slope * intercept +
+ (nRows + 1) * (2 * nRows + 1) * Math.pow(slope, 2) / 6);
+ }
+ }
+
+ @Override
+ protected void computeColSumsSq(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[_colIndexes[col]] += nRows * (Math.pow(intercept, 2) + (nRows + 1) * slope * intercept +
+ (nRows + 1) * (2 * nRows + 1) * Math.pow(slope, 2) / 6);
+ }
+ }
+
+ @Override
+ protected void computeRowSums(double[] c, int rl, int ru, double[] preAgg) {
+ double intercept_sum = 0;
+ for(double intercept : _coefficents[0])
+ intercept_sum += intercept;
+
+ double slope_sum = 0;
+ for(double slope : _coefficents[1])
+ slope_sum += slope;
+
+ for(int rix = rl; rix < ru; rix++)
+ c[rix] += intercept_sum + slope_sum * (rix + 1);
+ }
+
+ @Override
+ public int getNumValues() {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup rightMultByMatrix(MatrixBlock right) {
+ final int nColR = right.getNumColumns();
+ final int[] outputCols = Util.genColsIndices(nColR);
+
+ MatrixBlock result = new MatrixBlock(_numRows, nColR, false);
+ for(int j = 0; j < nColR; j++) {
+ double bias_accum = 0.0;
+ double slope_accum = 0.0;
+
+ for(int c = 0; c < _colIndexes.length; c++) {
+ bias_accum += right.getValue(_colIndexes[c], j) * _coefficents[0][c];
+ slope_accum += right.getValue(_colIndexes[c], j) * _coefficents[1][c];
+ }
+
+ for(int r = 0; r < _numRows; r++) {
+ result.setValue(r, j, bias_accum + (r+1) * slope_accum);
+ }
+ }
+
+ // returns an uncompressed ColGroup
+ return ColGroupUncompressed.create(result, outputCols);
+ }
+
+ @Override
+ public void tsmm(double[] ret, int numColumns, int nRows) {
+ // runs in O(tCol^2) since dot-products take O(1) time to compute when both vectors are linearly compressed
+ final int tCol = _colIndexes.length;
+
+ final double sumIndices = nRows * (nRows + 1)/2.0;
+ final double sumSquaredIndices = nRows * (nRows + 1) * (2*nRows + 1)/6.0;
+ for(int row = 0, offTmp = 0; row < tCol; row++, offTmp += tCol) {
+ final double alpha1 = nRows * _coefficents[0][row] + sumIndices * _coefficents[1][row];
+ final double alpha2 = sumIndices * _coefficents[0][row] + sumSquaredIndices * _coefficents[1][row];
+ final int offRet = _colIndexes[row] * numColumns;
+ for(int col = row; col < tCol; col++) {
+ ret[offRet + _colIndexes[col]] += alpha1 * _coefficents[0][col] + alpha2 * _coefficents[1][col];
+ }
+ }
+ }
+
+ @Override
+ public void leftMultByMatrixNoPreAgg(MatrixBlock matrix, MatrixBlock result, int rl, int ru, int cl, int cu) {
+ throw new DMLCompressionException("This method should never be called");
+ }
+
+ @Override
+ public void leftMultByAColGroup(AColGroup lhs, MatrixBlock result) {
+ if(lhs instanceof ColGroupEmpty) {
+ return;
+ }
+
+ MatrixBlock tmpRet = new MatrixBlock(lhs.getNumCols(), _colIndexes.length, 0);
+
+ if(lhs instanceof ColGroupUncompressed) {
+ ColGroupUncompressed lhsUC = (ColGroupUncompressed) lhs;
+ int numRowsLeft = lhsUC.getData().getNumRows();
+
+ double[] colSumsAndWeightedColSums = new double[2 * lhs.getNumCols()];
+ for(int j = 0, offTmp = 0; j < lhs.getNumCols(); j++, offTmp += 2) {
+ for(int i = 0; i < numRowsLeft; i++) {
+ colSumsAndWeightedColSums[offTmp] += lhs.getIdx(i, j);
+ colSumsAndWeightedColSums[offTmp + 1] += (i+1) * lhs.getIdx(i, j);
+ }
+ }
+
+ MatrixBlock sumMatrix = new MatrixBlock(lhs.getNumCols(), 2, colSumsAndWeightedColSums);
+ MatrixBlock coefficientMatrix = DataConverter.convertToMatrixBlock(_coefficents);
+
+ LibMatrixMult.matrixMult(sumMatrix, coefficientMatrix, tmpRet);
+ } else if(lhs instanceof ColGroupLinearFunctional) {
+ ColGroupLinearFunctional lhsLF = (ColGroupLinearFunctional) lhs;
+
+ final double sumIndices = _numRows * (_numRows + 1)/2.0;
+ final double sumSquaredIndices = _numRows * (_numRows + 1) * (2*_numRows + 1)/6.0;
+
+ MatrixBlock weightMatrix = new MatrixBlock(2, 2, new double[] {_numRows, sumIndices, sumIndices, sumSquaredIndices});
+ MatrixBlock coefficientMatrixLhs = DataConverter.convertToMatrixBlock(lhsLF._coefficents);
+ MatrixBlock coefficientMatrixRhs = DataConverter.convertToMatrixBlock(_coefficents);
+
+ coefficientMatrixLhs = LibMatrixReorg.transposeInPlace(coefficientMatrixLhs,
+ InfrastructureAnalyzer.getLocalParallelism());
+
+ // We simply compute a matrix multiplication chain in coefficient space, i.e.,
+ // t(L) %*% R = t(coeff(L)) %*% W %*% coeff(R)
+ // where W is a weight matrix capturing the size of the shared dimension (weightMatrix above)
+ // and coeff(X) denotes the 2 x n matrix of the m x n matrix X.
+ MatrixBlock tmp = new MatrixBlock(lhs.getNumCols(), 2, false);
+ LibMatrixMult.matrixMult(coefficientMatrixLhs, weightMatrix, tmp);
+ LibMatrixMult.matrixMult(tmp, coefficientMatrixRhs, tmpRet);
+ } else if(lhs instanceof APreAgg) {
+ // TODO: implement
+ throw new NotImplementedException();
+ } else {
+ throw new NotImplementedException();
+ }
+
+ final double[] resV = result.getDenseBlockValues();
+ if(tmpRet.isEmpty())
+ return;
+ else if(tmpRet.isInSparseFormat()) {
+ SparseBlock sb = tmpRet.getSparseBlock();
+ for(int row = 0; row < lhs._colIndexes.length; row++) {
+ if(sb.isEmpty(row))
+ continue;
+ final int apos = sb.pos(row);
+ final int alen = sb.size(row) + apos;
+ final int[] aix = sb.indexes(row);
+ final double[] avals = sb.values(row);
+ final int offRes = lhs._colIndexes[row] * result.getNumColumns();
+ for(int col = apos; col < alen; col++)
+ resV[offRes + _colIndexes[aix[col]]] += avals[col];
+ }
+ }
+ else {
+ double[] tmpRetV = tmpRet.getDenseBlockValues();
+ for(int row = 0; row < lhs.getNumCols(); row++) {
+ final int offRes = lhs._colIndexes[row] * result.getNumColumns();
+ final int offTmp = row * getNumCols();
+ for(int col = 0; col < getNumCols(); col++) {
+ resV[offRes + _colIndexes[col]] += tmpRetV[offTmp + col];
+ }
+ }
+ }
+ }
+
+ @Override
+ public void tsmmAColGroup(AColGroup other, MatrixBlock result) {
+ throw new DMLCompressionException("Should not be called");
+ }
+
+ @Override
+ protected AColGroup sliceSingleColumn(int idx) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected AColGroup sliceMultiColumns(int idStart, int idEnd, int[] outputCols) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup copy() {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public boolean containsValue(double pattern) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public long getNumberNonZeros(int nRows) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup replace(double pattern, double replace) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public void readFields(DataInput in) throws IOException {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public void write(DataOutput out) throws IOException {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public long getExactSizeOnDisk() {
+ long ret = super.getExactSizeOnDisk();
+ ret += _coefficents[0].length * _coefficents.length * 8L;
+ ret += 4L; // _numRows
+ return ret;
+ }
+
+ @Override
+ protected void computeProduct(double[] c, int nRows) {
+ c[0] = 1;
+ for(int colIndex : _colIndexes) {
+ double intercept = _coefficents[0][colIndex];
+ double slope = _coefficents[1][colIndex];
+ for(int i = 0; i < nRows; i++) {
+ c[0] *= intercept + slope * (i + 1);
+ }
+ }
+ }
+
+ @Override
+ protected void computeRowProduct(double[] c, int rl, int ru, double[] preAgg) {
+ for(int rix = rl; rix < ru; rix++) {
+ c[rix] = 1;
+ for(int colIndex : _colIndexes) {
+ double intercept = _coefficents[0][colIndex];
+ double slope = _coefficents[1][colIndex];
+ c[rix] *= intercept + slope * (rix + 1);
+ }
+ }
+ }
+
+ @Override
+ protected void computeColProduct(double[] c, int nRows) {
+ for(int colIndex : _colIndexes) {
+ c[colIndex] = 1;
Review Comment:
Do not set it
##########
src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupLinearFunctional.java:
##########
@@ -0,0 +1,516 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.sysds.runtime.compress.colgroup;
+
+import org.apache.commons.lang.NotImplementedException;
+import org.apache.sysds.runtime.compress.DMLCompressionException;
+import org.apache.sysds.runtime.compress.cost.ComputationCostEstimator;
+import org.apache.sysds.runtime.compress.utils.Util;
+import org.apache.sysds.runtime.controlprogram.parfor.stat.InfrastructureAnalyzer;
+import org.apache.sysds.runtime.data.DenseBlock;
+import org.apache.sysds.runtime.data.SparseBlock;
+import org.apache.sysds.runtime.functionobjects.Builtin;
+import org.apache.sysds.runtime.instructions.cp.CM_COV_Object;
+import org.apache.sysds.runtime.matrix.data.LibMatrixMult;
+import org.apache.sysds.runtime.matrix.data.LibMatrixReorg;
+import org.apache.sysds.runtime.matrix.data.MatrixBlock;
+import org.apache.sysds.runtime.matrix.operators.BinaryOperator;
+import org.apache.sysds.runtime.matrix.operators.CMOperator;
+import org.apache.sysds.runtime.matrix.operators.ScalarOperator;
+import org.apache.sysds.runtime.matrix.operators.UnaryOperator;
+import org.apache.sysds.runtime.util.DataConverter;
+
+import java.io.DataInput;
+import java.io.DataOutput;
+import java.io.IOException;
+import java.util.Arrays;
+
+public class ColGroupLinearFunctional extends AColGroupCompressed {
+
+ private static final long serialVersionUID = -2811822570758221975L;
+
+ protected double[][] _coefficents;
+
+ protected int _numRows;
+
+ /** Constructor for serialization */
+ protected ColGroupLinearFunctional() {
+ super();
+ }
+
+ /**
+ * Constructs a Linear Functional Column Group that compresses its content using a linear functional.
+ *
+ * @param colIndices The Column indexes for the column group.
+ * @param coefficents 2D-Array where coefficients[0] is the list of intercepts and coefficients[1] the list of slopes.
+ * @param numRows Number of rows encoded within this column group.
+ */
+ private ColGroupLinearFunctional(int[] colIndices, double[][] coefficents, int numRows) {
+ super(colIndices);
+ this._coefficents = coefficents;
+ this._numRows = numRows;
+ }
+
+ /**
+ * Generate a linear functional column group.
+ *
+ * @param colIndices The specific column indexes that is contained in this column group.
+ * @param coefficents 2D-Array where coefficients[0] is the list of intercepts and coefficients[1] the list of slopes.
+ * @param numRows Number of rows encoded within this column group.
+ * @return A LinearFunctional column group.
+ */
+ public static AColGroup create(int[] colIndices, double[][] coefficents, int numRows) {
+ if(coefficents.length != 2 || colIndices.length != coefficents[0].length)
+ throw new DMLCompressionException("Invalid size of values compared to columns");
+ return new ColGroupLinearFunctional(colIndices, coefficents, numRows);
+ }
+
+
+ @Override
+ protected void computeRowMxx(double[] c, Builtin builtin, int rl, int ru, double[] preAgg) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public CompressionType getCompType() {
+ return CompressionType.LinearFunctional;
+ }
+
+ @Override
+ public ColGroupType getColGroupType() {
+ return ColGroupType.LinearFunctional;
+ }
+
+ @Override
+ public double getMin() {
+ double min = Double.POSITIVE_INFINITY;
+
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ if(slope >= 0 && (intercept + slope) < min) {
+ min = intercept + slope;
+ }
+ else if(slope < 0 && (intercept + _numRows * slope) < min) {
+ min = intercept + _numRows * slope;
+ }
+ }
+
+ return min;
+ }
+
+ @Override
+ public double getMax() {
+ double max = Double.NEGATIVE_INFINITY;
+
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ if(slope >= 0 && (intercept + _numRows * slope) > max) {
+ max = intercept + _numRows * slope;
+ }
+ else if(slope < 0 && (intercept + slope) > max) {
+ max = intercept + slope;
+ }
+ }
+
+ return max;
+ }
+
+ @Override
+ public void decompressToDenseBlock(DenseBlock db, int rl, int ru, int offR, int offC) {
+ int offT = rl + offR;
+ final int nCol = _colIndexes.length;
+ int offS = rl * nCol;
+ for(int row = rl; row < ru; row++, offT++, offS += nCol) {
+ final double[] c = db.values(offT);
+ final int off = db.pos(offT) + offC;
+ for(int j = 0; j < nCol; j++)
+ c[off + _colIndexes[j]] += getIdx(row, j);
+ }
+ }
+
+ @Override
+ public void decompressToSparseBlock(SparseBlock ret, int rl, int ru, int offR, int offC) {
+ final int nCol = _colIndexes.length;
+ for(int i = rl, offT = rl + offR; i < ru; i++, offT++) {
+ for(int j = 0; j < nCol; j++)
+ ret.append(offT, _colIndexes[j] + offC, getIdx(i, j));
+ }
+ }
+
+ @Override
+ public double getIdx(int r, int colIdx) {
+ return _coefficents[0][colIdx] + _coefficents[1][colIdx] * (r + 1);
+ }
+
+ @Override
+ public AColGroup scalarOperation(ScalarOperator op) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup unaryOperation(UnaryOperator op) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup binaryRowOpLeft(BinaryOperator op, double[] v, boolean isRowSafe) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup binaryRowOpRight(BinaryOperator op, double[] v, boolean isRowSafe) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected double computeMxx(double c, Builtin builtin) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected void computeColMxx(double[] c, Builtin builtin) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected void computeSum(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[0] += nRows * (intercept + (nRows + 1) * slope / 2);
+ }
+ }
+
+ @Override
+ public void computeColSums(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[_colIndexes[col]] += nRows * (intercept + (nRows + 1) * slope / 2);
+ }
+ }
+
+ @Override
+ protected void computeSumSq(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[0] += nRows * (Math.pow(intercept, 2) + (nRows + 1) * slope * intercept +
+ (nRows + 1) * (2 * nRows + 1) * Math.pow(slope, 2) / 6);
+ }
+ }
+
+ @Override
+ protected void computeColSumsSq(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[_colIndexes[col]] += nRows * (Math.pow(intercept, 2) + (nRows + 1) * slope * intercept +
+ (nRows + 1) * (2 * nRows + 1) * Math.pow(slope, 2) / 6);
+ }
+ }
+
+ @Override
+ protected void computeRowSums(double[] c, int rl, int ru, double[] preAgg) {
+ double intercept_sum = 0;
+ for(double intercept : _coefficents[0])
+ intercept_sum += intercept;
+
+ double slope_sum = 0;
+ for(double slope : _coefficents[1])
+ slope_sum += slope;
+
+ for(int rix = rl; rix < ru; rix++)
+ c[rix] += intercept_sum + slope_sum * (rix + 1);
+ }
+
+ @Override
+ public int getNumValues() {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup rightMultByMatrix(MatrixBlock right) {
+ final int nColR = right.getNumColumns();
+ final int[] outputCols = Util.genColsIndices(nColR);
+
+ MatrixBlock result = new MatrixBlock(_numRows, nColR, false);
+ for(int j = 0; j < nColR; j++) {
+ double bias_accum = 0.0;
+ double slope_accum = 0.0;
+
+ for(int c = 0; c < _colIndexes.length; c++) {
+ bias_accum += right.getValue(_colIndexes[c], j) * _coefficents[0][c];
+ slope_accum += right.getValue(_colIndexes[c], j) * _coefficents[1][c];
+ }
+
+ for(int r = 0; r < _numRows; r++) {
+ result.setValue(r, j, bias_accum + (r+1) * slope_accum);
+ }
+ }
+
+ // returns an uncompressed ColGroup
+ return ColGroupUncompressed.create(result, outputCols);
+ }
+
+ @Override
+ public void tsmm(double[] ret, int numColumns, int nRows) {
+ // runs in O(tCol^2) since dot-products take O(1) time to compute when both vectors are linearly compressed
+ final int tCol = _colIndexes.length;
+
+ final double sumIndices = nRows * (nRows + 1)/2.0;
+ final double sumSquaredIndices = nRows * (nRows + 1) * (2*nRows + 1)/6.0;
+ for(int row = 0, offTmp = 0; row < tCol; row++, offTmp += tCol) {
+ final double alpha1 = nRows * _coefficents[0][row] + sumIndices * _coefficents[1][row];
+ final double alpha2 = sumIndices * _coefficents[0][row] + sumSquaredIndices * _coefficents[1][row];
+ final int offRet = _colIndexes[row] * numColumns;
+ for(int col = row; col < tCol; col++) {
+ ret[offRet + _colIndexes[col]] += alpha1 * _coefficents[0][col] + alpha2 * _coefficents[1][col];
+ }
+ }
+ }
+
+ @Override
+ public void leftMultByMatrixNoPreAgg(MatrixBlock matrix, MatrixBlock result, int rl, int ru, int cl, int cu) {
+ throw new DMLCompressionException("This method should never be called");
+ }
+
+ @Override
+ public void leftMultByAColGroup(AColGroup lhs, MatrixBlock result) {
+ if(lhs instanceof ColGroupEmpty) {
+ return;
+ }
+
+ MatrixBlock tmpRet = new MatrixBlock(lhs.getNumCols(), _colIndexes.length, 0);
+
+ if(lhs instanceof ColGroupUncompressed) {
+ ColGroupUncompressed lhsUC = (ColGroupUncompressed) lhs;
+ int numRowsLeft = lhsUC.getData().getNumRows();
+
+ double[] colSumsAndWeightedColSums = new double[2 * lhs.getNumCols()];
+ for(int j = 0, offTmp = 0; j < lhs.getNumCols(); j++, offTmp += 2) {
+ for(int i = 0; i < numRowsLeft; i++) {
+ colSumsAndWeightedColSums[offTmp] += lhs.getIdx(i, j);
+ colSumsAndWeightedColSums[offTmp + 1] += (i+1) * lhs.getIdx(i, j);
+ }
+ }
+
+ MatrixBlock sumMatrix = new MatrixBlock(lhs.getNumCols(), 2, colSumsAndWeightedColSums);
+ MatrixBlock coefficientMatrix = DataConverter.convertToMatrixBlock(_coefficents);
+
+ LibMatrixMult.matrixMult(sumMatrix, coefficientMatrix, tmpRet);
+ } else if(lhs instanceof ColGroupLinearFunctional) {
+ ColGroupLinearFunctional lhsLF = (ColGroupLinearFunctional) lhs;
+
+ final double sumIndices = _numRows * (_numRows + 1)/2.0;
+ final double sumSquaredIndices = _numRows * (_numRows + 1) * (2*_numRows + 1)/6.0;
+
+ MatrixBlock weightMatrix = new MatrixBlock(2, 2, new double[] {_numRows, sumIndices, sumIndices, sumSquaredIndices});
+ MatrixBlock coefficientMatrixLhs = DataConverter.convertToMatrixBlock(lhsLF._coefficents);
+ MatrixBlock coefficientMatrixRhs = DataConverter.convertToMatrixBlock(_coefficents);
+
+ coefficientMatrixLhs = LibMatrixReorg.transposeInPlace(coefficientMatrixLhs,
+ InfrastructureAnalyzer.getLocalParallelism());
+
+ // We simply compute a matrix multiplication chain in coefficient space, i.e.,
+ // t(L) %*% R = t(coeff(L)) %*% W %*% coeff(R)
+ // where W is a weight matrix capturing the size of the shared dimension (weightMatrix above)
+ // and coeff(X) denotes the 2 x n matrix of the m x n matrix X.
+ MatrixBlock tmp = new MatrixBlock(lhs.getNumCols(), 2, false);
+ LibMatrixMult.matrixMult(coefficientMatrixLhs, weightMatrix, tmp);
+ LibMatrixMult.matrixMult(tmp, coefficientMatrixRhs, tmpRet);
+ } else if(lhs instanceof APreAgg) {
+ // TODO: implement
+ throw new NotImplementedException();
+ } else {
+ throw new NotImplementedException();
+ }
+
+ final double[] resV = result.getDenseBlockValues();
+ if(tmpRet.isEmpty())
+ return;
+ else if(tmpRet.isInSparseFormat()) {
+ SparseBlock sb = tmpRet.getSparseBlock();
+ for(int row = 0; row < lhs._colIndexes.length; row++) {
+ if(sb.isEmpty(row))
+ continue;
+ final int apos = sb.pos(row);
+ final int alen = sb.size(row) + apos;
+ final int[] aix = sb.indexes(row);
+ final double[] avals = sb.values(row);
+ final int offRes = lhs._colIndexes[row] * result.getNumColumns();
+ for(int col = apos; col < alen; col++)
+ resV[offRes + _colIndexes[aix[col]]] += avals[col];
+ }
+ }
+ else {
+ double[] tmpRetV = tmpRet.getDenseBlockValues();
+ for(int row = 0; row < lhs.getNumCols(); row++) {
+ final int offRes = lhs._colIndexes[row] * result.getNumColumns();
+ final int offTmp = row * getNumCols();
+ for(int col = 0; col < getNumCols(); col++) {
+ resV[offRes + _colIndexes[col]] += tmpRetV[offTmp + col];
+ }
+ }
+ }
+ }
+
+ @Override
+ public void tsmmAColGroup(AColGroup other, MatrixBlock result) {
+ throw new DMLCompressionException("Should not be called");
+ }
+
+ @Override
+ protected AColGroup sliceSingleColumn(int idx) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected AColGroup sliceMultiColumns(int idStart, int idEnd, int[] outputCols) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup copy() {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public boolean containsValue(double pattern) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public long getNumberNonZeros(int nRows) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup replace(double pattern, double replace) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public void readFields(DataInput in) throws IOException {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public void write(DataOutput out) throws IOException {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public long getExactSizeOnDisk() {
+ long ret = super.getExactSizeOnDisk();
+ ret += _coefficents[0].length * _coefficents.length * 8L;
+ ret += 4L; // _numRows
+ return ret;
+ }
+
+ @Override
+ protected void computeProduct(double[] c, int nRows) {
+ c[0] = 1;
Review Comment:
furthermore you could add a speedup, by adding a containsZero method that detects if any of the values contained in the function is zero return zero
##########
src/test/java/org/apache/sysds/test/component/compress/colgroup/ColGroupLinearFunctionalTest.java:
##########
@@ -0,0 +1,547 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.sysds.test.component.compress.colgroup;
+
+import org.apache.commons.logging.Log;
+import org.apache.commons.logging.LogFactory;
+import org.apache.sysds.runtime.DMLRuntimeException;
+import org.apache.sysds.runtime.compress.CompressionSettings;
+import org.apache.sysds.runtime.compress.CompressionSettingsBuilder;
+import org.apache.sysds.runtime.compress.colgroup.AColGroup;
+import org.apache.sysds.runtime.compress.colgroup.ColGroupFactory;
+import org.apache.sysds.runtime.compress.colgroup.ColGroupUncompressed;
+import org.apache.sysds.runtime.compress.estim.CompressedSizeEstimatorExact;
+import org.apache.sysds.runtime.compress.estim.CompressedSizeInfo;
+import org.apache.sysds.runtime.compress.estim.CompressedSizeInfoColGroup;
+import org.apache.sysds.runtime.controlprogram.parfor.stat.InfrastructureAnalyzer;
+import org.apache.sysds.runtime.functionobjects.*;
+import org.apache.sysds.runtime.matrix.data.LibMatrixMult;
+import org.apache.sysds.runtime.matrix.data.LibMatrixReorg;
+import org.apache.sysds.runtime.matrix.data.MatrixBlock;
+import org.apache.sysds.runtime.matrix.operators.AggregateOperator;
+import org.apache.sysds.runtime.matrix.operators.AggregateUnaryOperator;
+import org.apache.sysds.runtime.util.DataConverter;
+import org.junit.Assert;
+import org.junit.Test;
+
+import java.util.EnumSet;
+import java.util.Random;
+
+public class ColGroupLinearFunctionalTest {
Review Comment:
Also to make me really happy you would test with different input linear compressions, and this is hard with your current design while with parameterized tests it would be easy.
For instance make a line that is constant zero, what happens
line constant other value.
line increasing
line decreasing
two dimensions one constant other increasing.
etc
##########
src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupLinearFunctional.java:
##########
@@ -0,0 +1,516 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.sysds.runtime.compress.colgroup;
+
+import org.apache.commons.lang.NotImplementedException;
+import org.apache.sysds.runtime.compress.DMLCompressionException;
+import org.apache.sysds.runtime.compress.cost.ComputationCostEstimator;
+import org.apache.sysds.runtime.compress.utils.Util;
+import org.apache.sysds.runtime.controlprogram.parfor.stat.InfrastructureAnalyzer;
+import org.apache.sysds.runtime.data.DenseBlock;
+import org.apache.sysds.runtime.data.SparseBlock;
+import org.apache.sysds.runtime.functionobjects.Builtin;
+import org.apache.sysds.runtime.instructions.cp.CM_COV_Object;
+import org.apache.sysds.runtime.matrix.data.LibMatrixMult;
+import org.apache.sysds.runtime.matrix.data.LibMatrixReorg;
+import org.apache.sysds.runtime.matrix.data.MatrixBlock;
+import org.apache.sysds.runtime.matrix.operators.BinaryOperator;
+import org.apache.sysds.runtime.matrix.operators.CMOperator;
+import org.apache.sysds.runtime.matrix.operators.ScalarOperator;
+import org.apache.sysds.runtime.matrix.operators.UnaryOperator;
+import org.apache.sysds.runtime.util.DataConverter;
+
+import java.io.DataInput;
+import java.io.DataOutput;
+import java.io.IOException;
+import java.util.Arrays;
+
+public class ColGroupLinearFunctional extends AColGroupCompressed {
+
+ private static final long serialVersionUID = -2811822570758221975L;
+
+ protected double[][] _coefficents;
+
+ protected int _numRows;
+
+ /** Constructor for serialization */
+ protected ColGroupLinearFunctional() {
+ super();
+ }
+
+ /**
+ * Constructs a Linear Functional Column Group that compresses its content using a linear functional.
+ *
+ * @param colIndices The Column indexes for the column group.
+ * @param coefficents 2D-Array where coefficients[0] is the list of intercepts and coefficients[1] the list of slopes.
+ * @param numRows Number of rows encoded within this column group.
+ */
+ private ColGroupLinearFunctional(int[] colIndices, double[][] coefficents, int numRows) {
+ super(colIndices);
+ this._coefficents = coefficents;
+ this._numRows = numRows;
+ }
+
+ /**
+ * Generate a linear functional column group.
+ *
+ * @param colIndices The specific column indexes that is contained in this column group.
+ * @param coefficents 2D-Array where coefficients[0] is the list of intercepts and coefficients[1] the list of slopes.
+ * @param numRows Number of rows encoded within this column group.
+ * @return A LinearFunctional column group.
+ */
+ public static AColGroup create(int[] colIndices, double[][] coefficents, int numRows) {
+ if(coefficents.length != 2 || colIndices.length != coefficents[0].length)
+ throw new DMLCompressionException("Invalid size of values compared to columns");
+ return new ColGroupLinearFunctional(colIndices, coefficents, numRows);
+ }
+
+
+ @Override
+ protected void computeRowMxx(double[] c, Builtin builtin, int rl, int ru, double[] preAgg) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public CompressionType getCompType() {
+ return CompressionType.LinearFunctional;
+ }
+
+ @Override
+ public ColGroupType getColGroupType() {
+ return ColGroupType.LinearFunctional;
+ }
+
+ @Override
+ public double getMin() {
+ double min = Double.POSITIVE_INFINITY;
+
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ if(slope >= 0 && (intercept + slope) < min) {
+ min = intercept + slope;
+ }
+ else if(slope < 0 && (intercept + _numRows * slope) < min) {
+ min = intercept + _numRows * slope;
+ }
+ }
+
+ return min;
+ }
+
+ @Override
+ public double getMax() {
+ double max = Double.NEGATIVE_INFINITY;
+
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ if(slope >= 0 && (intercept + _numRows * slope) > max) {
+ max = intercept + _numRows * slope;
+ }
+ else if(slope < 0 && (intercept + slope) > max) {
+ max = intercept + slope;
+ }
+ }
+
+ return max;
+ }
+
+ @Override
+ public void decompressToDenseBlock(DenseBlock db, int rl, int ru, int offR, int offC) {
+ int offT = rl + offR;
+ final int nCol = _colIndexes.length;
+ int offS = rl * nCol;
+ for(int row = rl; row < ru; row++, offT++, offS += nCol) {
+ final double[] c = db.values(offT);
+ final int off = db.pos(offT) + offC;
+ for(int j = 0; j < nCol; j++)
+ c[off + _colIndexes[j]] += getIdx(row, j);
+ }
+ }
+
+ @Override
+ public void decompressToSparseBlock(SparseBlock ret, int rl, int ru, int offR, int offC) {
+ final int nCol = _colIndexes.length;
+ for(int i = rl, offT = rl + offR; i < ru; i++, offT++) {
+ for(int j = 0; j < nCol; j++)
+ ret.append(offT, _colIndexes[j] + offC, getIdx(i, j));
+ }
+ }
+
+ @Override
+ public double getIdx(int r, int colIdx) {
+ return _coefficents[0][colIdx] + _coefficents[1][colIdx] * (r + 1);
+ }
+
+ @Override
+ public AColGroup scalarOperation(ScalarOperator op) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup unaryOperation(UnaryOperator op) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup binaryRowOpLeft(BinaryOperator op, double[] v, boolean isRowSafe) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup binaryRowOpRight(BinaryOperator op, double[] v, boolean isRowSafe) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected double computeMxx(double c, Builtin builtin) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected void computeColMxx(double[] c, Builtin builtin) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected void computeSum(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[0] += nRows * (intercept + (nRows + 1) * slope / 2);
+ }
+ }
+
+ @Override
+ public void computeColSums(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[_colIndexes[col]] += nRows * (intercept + (nRows + 1) * slope / 2);
+ }
+ }
+
+ @Override
+ protected void computeSumSq(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[0] += nRows * (Math.pow(intercept, 2) + (nRows + 1) * slope * intercept +
+ (nRows + 1) * (2 * nRows + 1) * Math.pow(slope, 2) / 6);
+ }
+ }
+
+ @Override
+ protected void computeColSumsSq(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[_colIndexes[col]] += nRows * (Math.pow(intercept, 2) + (nRows + 1) * slope * intercept +
+ (nRows + 1) * (2 * nRows + 1) * Math.pow(slope, 2) / 6);
+ }
+ }
+
+ @Override
+ protected void computeRowSums(double[] c, int rl, int ru, double[] preAgg) {
+ double intercept_sum = 0;
+ for(double intercept : _coefficents[0])
+ intercept_sum += intercept;
+
+ double slope_sum = 0;
+ for(double slope : _coefficents[1])
+ slope_sum += slope;
+
+ for(int rix = rl; rix < ru; rix++)
+ c[rix] += intercept_sum + slope_sum * (rix + 1);
+ }
+
+ @Override
+ public int getNumValues() {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup rightMultByMatrix(MatrixBlock right) {
+ final int nColR = right.getNumColumns();
+ final int[] outputCols = Util.genColsIndices(nColR);
+
+ MatrixBlock result = new MatrixBlock(_numRows, nColR, false);
+ for(int j = 0; j < nColR; j++) {
+ double bias_accum = 0.0;
+ double slope_accum = 0.0;
+
+ for(int c = 0; c < _colIndexes.length; c++) {
+ bias_accum += right.getValue(_colIndexes[c], j) * _coefficents[0][c];
+ slope_accum += right.getValue(_colIndexes[c], j) * _coefficents[1][c];
+ }
+
+ for(int r = 0; r < _numRows; r++) {
+ result.setValue(r, j, bias_accum + (r+1) * slope_accum);
+ }
+ }
+
+ // returns an uncompressed ColGroup
+ return ColGroupUncompressed.create(result, outputCols);
+ }
+
+ @Override
+ public void tsmm(double[] ret, int numColumns, int nRows) {
+ // runs in O(tCol^2) since dot-products take O(1) time to compute when both vectors are linearly compressed
+ final int tCol = _colIndexes.length;
+
+ final double sumIndices = nRows * (nRows + 1)/2.0;
+ final double sumSquaredIndices = nRows * (nRows + 1) * (2*nRows + 1)/6.0;
+ for(int row = 0, offTmp = 0; row < tCol; row++, offTmp += tCol) {
+ final double alpha1 = nRows * _coefficents[0][row] + sumIndices * _coefficents[1][row];
+ final double alpha2 = sumIndices * _coefficents[0][row] + sumSquaredIndices * _coefficents[1][row];
+ final int offRet = _colIndexes[row] * numColumns;
+ for(int col = row; col < tCol; col++) {
+ ret[offRet + _colIndexes[col]] += alpha1 * _coefficents[0][col] + alpha2 * _coefficents[1][col];
+ }
+ }
+ }
+
+ @Override
+ public void leftMultByMatrixNoPreAgg(MatrixBlock matrix, MatrixBlock result, int rl, int ru, int cl, int cu) {
+ throw new DMLCompressionException("This method should never be called");
+ }
+
+ @Override
+ public void leftMultByAColGroup(AColGroup lhs, MatrixBlock result) {
+ if(lhs instanceof ColGroupEmpty) {
+ return;
+ }
+
+ MatrixBlock tmpRet = new MatrixBlock(lhs.getNumCols(), _colIndexes.length, 0);
+
+ if(lhs instanceof ColGroupUncompressed) {
+ ColGroupUncompressed lhsUC = (ColGroupUncompressed) lhs;
+ int numRowsLeft = lhsUC.getData().getNumRows();
+
+ double[] colSumsAndWeightedColSums = new double[2 * lhs.getNumCols()];
+ for(int j = 0, offTmp = 0; j < lhs.getNumCols(); j++, offTmp += 2) {
+ for(int i = 0; i < numRowsLeft; i++) {
+ colSumsAndWeightedColSums[offTmp] += lhs.getIdx(i, j);
+ colSumsAndWeightedColSums[offTmp + 1] += (i+1) * lhs.getIdx(i, j);
+ }
+ }
+
+ MatrixBlock sumMatrix = new MatrixBlock(lhs.getNumCols(), 2, colSumsAndWeightedColSums);
+ MatrixBlock coefficientMatrix = DataConverter.convertToMatrixBlock(_coefficents);
+
+ LibMatrixMult.matrixMult(sumMatrix, coefficientMatrix, tmpRet);
+ } else if(lhs instanceof ColGroupLinearFunctional) {
+ ColGroupLinearFunctional lhsLF = (ColGroupLinearFunctional) lhs;
+
+ final double sumIndices = _numRows * (_numRows + 1)/2.0;
+ final double sumSquaredIndices = _numRows * (_numRows + 1) * (2*_numRows + 1)/6.0;
+
+ MatrixBlock weightMatrix = new MatrixBlock(2, 2, new double[] {_numRows, sumIndices, sumIndices, sumSquaredIndices});
+ MatrixBlock coefficientMatrixLhs = DataConverter.convertToMatrixBlock(lhsLF._coefficents);
+ MatrixBlock coefficientMatrixRhs = DataConverter.convertToMatrixBlock(_coefficents);
+
+ coefficientMatrixLhs = LibMatrixReorg.transposeInPlace(coefficientMatrixLhs,
+ InfrastructureAnalyzer.getLocalParallelism());
+
+ // We simply compute a matrix multiplication chain in coefficient space, i.e.,
+ // t(L) %*% R = t(coeff(L)) %*% W %*% coeff(R)
+ // where W is a weight matrix capturing the size of the shared dimension (weightMatrix above)
+ // and coeff(X) denotes the 2 x n matrix of the m x n matrix X.
+ MatrixBlock tmp = new MatrixBlock(lhs.getNumCols(), 2, false);
+ LibMatrixMult.matrixMult(coefficientMatrixLhs, weightMatrix, tmp);
+ LibMatrixMult.matrixMult(tmp, coefficientMatrixRhs, tmpRet);
+ } else if(lhs instanceof APreAgg) {
+ // TODO: implement
+ throw new NotImplementedException();
+ } else {
+ throw new NotImplementedException();
+ }
+
+ final double[] resV = result.getDenseBlockValues();
+ if(tmpRet.isEmpty())
+ return;
+ else if(tmpRet.isInSparseFormat()) {
+ SparseBlock sb = tmpRet.getSparseBlock();
+ for(int row = 0; row < lhs._colIndexes.length; row++) {
+ if(sb.isEmpty(row))
+ continue;
+ final int apos = sb.pos(row);
+ final int alen = sb.size(row) + apos;
+ final int[] aix = sb.indexes(row);
+ final double[] avals = sb.values(row);
+ final int offRes = lhs._colIndexes[row] * result.getNumColumns();
+ for(int col = apos; col < alen; col++)
+ resV[offRes + _colIndexes[aix[col]]] += avals[col];
+ }
+ }
+ else {
+ double[] tmpRetV = tmpRet.getDenseBlockValues();
+ for(int row = 0; row < lhs.getNumCols(); row++) {
+ final int offRes = lhs._colIndexes[row] * result.getNumColumns();
+ final int offTmp = row * getNumCols();
+ for(int col = 0; col < getNumCols(); col++) {
+ resV[offRes + _colIndexes[col]] += tmpRetV[offTmp + col];
+ }
+ }
+ }
+ }
+
+ @Override
+ public void tsmmAColGroup(AColGroup other, MatrixBlock result) {
+ throw new DMLCompressionException("Should not be called");
+ }
+
+ @Override
+ protected AColGroup sliceSingleColumn(int idx) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected AColGroup sliceMultiColumns(int idStart, int idEnd, int[] outputCols) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup copy() {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public boolean containsValue(double pattern) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public long getNumberNonZeros(int nRows) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup replace(double pattern, double replace) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public void readFields(DataInput in) throws IOException {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public void write(DataOutput out) throws IOException {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public long getExactSizeOnDisk() {
+ long ret = super.getExactSizeOnDisk();
+ ret += _coefficents[0].length * _coefficents.length * 8L;
+ ret += 4L; // _numRows
+ return ret;
+ }
+
+ @Override
+ protected void computeProduct(double[] c, int nRows) {
+ c[0] = 1;
+ for(int colIndex : _colIndexes) {
+ double intercept = _coefficents[0][colIndex];
+ double slope = _coefficents[1][colIndex];
+ for(int i = 0; i < nRows; i++) {
+ c[0] *= intercept + slope * (i + 1);
+ }
+ }
+ }
+
+ @Override
+ protected void computeRowProduct(double[] c, int rl, int ru, double[] preAgg) {
+ for(int rix = rl; rix < ru; rix++) {
+ c[rix] = 1;
+ for(int colIndex : _colIndexes) {
+ double intercept = _coefficents[0][colIndex];
+ double slope = _coefficents[1][colIndex];
+ c[rix] *= intercept + slope * (rix + 1);
+ }
+ }
+ }
+
+ @Override
+ protected void computeColProduct(double[] c, int nRows) {
+ for(int colIndex : _colIndexes) {
+ c[colIndex] = 1;
+ double intercept = _coefficents[0][colIndex];
+ double slope = _coefficents[1][colIndex];
+ for(int i = 0; i < nRows; i++) {
+ c[colIndex] *= intercept + slope * (i + 1);
+ }
+ }
+ }
+
+ @Override
+ protected double[] preAggSumRows() {
+ throw new NotImplementedException();
Review Comment:
use these methods to allocate what you want to use in the SumRows call.
for instance you currently have:
```
@Override
protected void computeRowSums(double[] c, int rl, int ru, double[] preAgg) {
double intercept_sum = 0;
for(double intercept : _coefficents[0])
intercept_sum += intercept;
double slope_sum = 0;
for(double slope : _coefficents[1])
slope_sum += slope;
for(int rix = rl; rix < ru; rix++)
c[rix] += intercept_sum + slope_sum * (rix + 1);
}
```
instead of processing all the coefficients in all calls to all rl to ru,
preAggregate the first two for loops into the double[] array to contain two values `double[]{intercept_sum, slope_sum}`
this makes the parallelization of different row ranges trivial, and much much much faster.
##########
src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupLinearFunctional.java:
##########
@@ -0,0 +1,516 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.sysds.runtime.compress.colgroup;
+
+import org.apache.commons.lang.NotImplementedException;
+import org.apache.sysds.runtime.compress.DMLCompressionException;
+import org.apache.sysds.runtime.compress.cost.ComputationCostEstimator;
+import org.apache.sysds.runtime.compress.utils.Util;
+import org.apache.sysds.runtime.controlprogram.parfor.stat.InfrastructureAnalyzer;
+import org.apache.sysds.runtime.data.DenseBlock;
+import org.apache.sysds.runtime.data.SparseBlock;
+import org.apache.sysds.runtime.functionobjects.Builtin;
+import org.apache.sysds.runtime.instructions.cp.CM_COV_Object;
+import org.apache.sysds.runtime.matrix.data.LibMatrixMult;
+import org.apache.sysds.runtime.matrix.data.LibMatrixReorg;
+import org.apache.sysds.runtime.matrix.data.MatrixBlock;
+import org.apache.sysds.runtime.matrix.operators.BinaryOperator;
+import org.apache.sysds.runtime.matrix.operators.CMOperator;
+import org.apache.sysds.runtime.matrix.operators.ScalarOperator;
+import org.apache.sysds.runtime.matrix.operators.UnaryOperator;
+import org.apache.sysds.runtime.util.DataConverter;
+
+import java.io.DataInput;
+import java.io.DataOutput;
+import java.io.IOException;
+import java.util.Arrays;
+
+public class ColGroupLinearFunctional extends AColGroupCompressed {
+
+ private static final long serialVersionUID = -2811822570758221975L;
+
+ protected double[][] _coefficents;
+
+ protected int _numRows;
+
+ /** Constructor for serialization */
+ protected ColGroupLinearFunctional() {
+ super();
+ }
+
+ /**
+ * Constructs a Linear Functional Column Group that compresses its content using a linear functional.
+ *
+ * @param colIndices The Column indexes for the column group.
+ * @param coefficents 2D-Array where coefficients[0] is the list of intercepts and coefficients[1] the list of slopes.
+ * @param numRows Number of rows encoded within this column group.
+ */
+ private ColGroupLinearFunctional(int[] colIndices, double[][] coefficents, int numRows) {
+ super(colIndices);
+ this._coefficents = coefficents;
+ this._numRows = numRows;
+ }
+
+ /**
+ * Generate a linear functional column group.
+ *
+ * @param colIndices The specific column indexes that is contained in this column group.
+ * @param coefficents 2D-Array where coefficients[0] is the list of intercepts and coefficients[1] the list of slopes.
+ * @param numRows Number of rows encoded within this column group.
+ * @return A LinearFunctional column group.
+ */
+ public static AColGroup create(int[] colIndices, double[][] coefficents, int numRows) {
+ if(coefficents.length != 2 || colIndices.length != coefficents[0].length)
+ throw new DMLCompressionException("Invalid size of values compared to columns");
+ return new ColGroupLinearFunctional(colIndices, coefficents, numRows);
+ }
+
+
+ @Override
+ protected void computeRowMxx(double[] c, Builtin builtin, int rl, int ru, double[] preAgg) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public CompressionType getCompType() {
+ return CompressionType.LinearFunctional;
+ }
+
+ @Override
+ public ColGroupType getColGroupType() {
+ return ColGroupType.LinearFunctional;
+ }
+
+ @Override
+ public double getMin() {
+ double min = Double.POSITIVE_INFINITY;
+
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ if(slope >= 0 && (intercept + slope) < min) {
+ min = intercept + slope;
+ }
+ else if(slope < 0 && (intercept + _numRows * slope) < min) {
+ min = intercept + _numRows * slope;
+ }
+ }
+
+ return min;
+ }
+
+ @Override
+ public double getMax() {
+ double max = Double.NEGATIVE_INFINITY;
+
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ if(slope >= 0 && (intercept + _numRows * slope) > max) {
+ max = intercept + _numRows * slope;
+ }
+ else if(slope < 0 && (intercept + slope) > max) {
+ max = intercept + slope;
+ }
+ }
+
+ return max;
+ }
+
+ @Override
+ public void decompressToDenseBlock(DenseBlock db, int rl, int ru, int offR, int offC) {
+ int offT = rl + offR;
+ final int nCol = _colIndexes.length;
+ int offS = rl * nCol;
+ for(int row = rl; row < ru; row++, offT++, offS += nCol) {
+ final double[] c = db.values(offT);
+ final int off = db.pos(offT) + offC;
+ for(int j = 0; j < nCol; j++)
+ c[off + _colIndexes[j]] += getIdx(row, j);
+ }
+ }
+
+ @Override
+ public void decompressToSparseBlock(SparseBlock ret, int rl, int ru, int offR, int offC) {
+ final int nCol = _colIndexes.length;
+ for(int i = rl, offT = rl + offR; i < ru; i++, offT++) {
+ for(int j = 0; j < nCol; j++)
+ ret.append(offT, _colIndexes[j] + offC, getIdx(i, j));
+ }
+ }
+
+ @Override
+ public double getIdx(int r, int colIdx) {
+ return _coefficents[0][colIdx] + _coefficents[1][colIdx] * (r + 1);
+ }
+
+ @Override
+ public AColGroup scalarOperation(ScalarOperator op) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup unaryOperation(UnaryOperator op) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup binaryRowOpLeft(BinaryOperator op, double[] v, boolean isRowSafe) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup binaryRowOpRight(BinaryOperator op, double[] v, boolean isRowSafe) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected double computeMxx(double c, Builtin builtin) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected void computeColMxx(double[] c, Builtin builtin) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected void computeSum(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[0] += nRows * (intercept + (nRows + 1) * slope / 2);
+ }
+ }
+
+ @Override
+ public void computeColSums(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[_colIndexes[col]] += nRows * (intercept + (nRows + 1) * slope / 2);
+ }
+ }
+
+ @Override
+ protected void computeSumSq(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[0] += nRows * (Math.pow(intercept, 2) + (nRows + 1) * slope * intercept +
+ (nRows + 1) * (2 * nRows + 1) * Math.pow(slope, 2) / 6);
+ }
+ }
+
+ @Override
+ protected void computeColSumsSq(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[_colIndexes[col]] += nRows * (Math.pow(intercept, 2) + (nRows + 1) * slope * intercept +
+ (nRows + 1) * (2 * nRows + 1) * Math.pow(slope, 2) / 6);
+ }
+ }
+
+ @Override
+ protected void computeRowSums(double[] c, int rl, int ru, double[] preAgg) {
+ double intercept_sum = 0;
+ for(double intercept : _coefficents[0])
+ intercept_sum += intercept;
+
+ double slope_sum = 0;
+ for(double slope : _coefficents[1])
+ slope_sum += slope;
+
+ for(int rix = rl; rix < ru; rix++)
+ c[rix] += intercept_sum + slope_sum * (rix + 1);
+ }
+
+ @Override
+ public int getNumValues() {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup rightMultByMatrix(MatrixBlock right) {
+ final int nColR = right.getNumColumns();
+ final int[] outputCols = Util.genColsIndices(nColR);
+
+ MatrixBlock result = new MatrixBlock(_numRows, nColR, false);
+ for(int j = 0; j < nColR; j++) {
+ double bias_accum = 0.0;
+ double slope_accum = 0.0;
+
+ for(int c = 0; c < _colIndexes.length; c++) {
+ bias_accum += right.getValue(_colIndexes[c], j) * _coefficents[0][c];
+ slope_accum += right.getValue(_colIndexes[c], j) * _coefficents[1][c];
+ }
+
+ for(int r = 0; r < _numRows; r++) {
+ result.setValue(r, j, bias_accum + (r+1) * slope_accum);
+ }
+ }
+
+ // returns an uncompressed ColGroup
+ return ColGroupUncompressed.create(result, outputCols);
+ }
+
+ @Override
+ public void tsmm(double[] ret, int numColumns, int nRows) {
+ // runs in O(tCol^2) since dot-products take O(1) time to compute when both vectors are linearly compressed
+ final int tCol = _colIndexes.length;
+
+ final double sumIndices = nRows * (nRows + 1)/2.0;
+ final double sumSquaredIndices = nRows * (nRows + 1) * (2*nRows + 1)/6.0;
+ for(int row = 0, offTmp = 0; row < tCol; row++, offTmp += tCol) {
+ final double alpha1 = nRows * _coefficents[0][row] + sumIndices * _coefficents[1][row];
+ final double alpha2 = sumIndices * _coefficents[0][row] + sumSquaredIndices * _coefficents[1][row];
+ final int offRet = _colIndexes[row] * numColumns;
+ for(int col = row; col < tCol; col++) {
+ ret[offRet + _colIndexes[col]] += alpha1 * _coefficents[0][col] + alpha2 * _coefficents[1][col];
+ }
+ }
+ }
+
+ @Override
+ public void leftMultByMatrixNoPreAgg(MatrixBlock matrix, MatrixBlock result, int rl, int ru, int cl, int cu) {
+ throw new DMLCompressionException("This method should never be called");
+ }
+
+ @Override
+ public void leftMultByAColGroup(AColGroup lhs, MatrixBlock result) {
+ if(lhs instanceof ColGroupEmpty) {
+ return;
+ }
+
+ MatrixBlock tmpRet = new MatrixBlock(lhs.getNumCols(), _colIndexes.length, 0);
+
+ if(lhs instanceof ColGroupUncompressed) {
+ ColGroupUncompressed lhsUC = (ColGroupUncompressed) lhs;
+ int numRowsLeft = lhsUC.getData().getNumRows();
+
+ double[] colSumsAndWeightedColSums = new double[2 * lhs.getNumCols()];
+ for(int j = 0, offTmp = 0; j < lhs.getNumCols(); j++, offTmp += 2) {
+ for(int i = 0; i < numRowsLeft; i++) {
+ colSumsAndWeightedColSums[offTmp] += lhs.getIdx(i, j);
+ colSumsAndWeightedColSums[offTmp + 1] += (i+1) * lhs.getIdx(i, j);
+ }
+ }
+
+ MatrixBlock sumMatrix = new MatrixBlock(lhs.getNumCols(), 2, colSumsAndWeightedColSums);
+ MatrixBlock coefficientMatrix = DataConverter.convertToMatrixBlock(_coefficents);
+
+ LibMatrixMult.matrixMult(sumMatrix, coefficientMatrix, tmpRet);
+ } else if(lhs instanceof ColGroupLinearFunctional) {
+ ColGroupLinearFunctional lhsLF = (ColGroupLinearFunctional) lhs;
+
+ final double sumIndices = _numRows * (_numRows + 1)/2.0;
+ final double sumSquaredIndices = _numRows * (_numRows + 1) * (2*_numRows + 1)/6.0;
+
+ MatrixBlock weightMatrix = new MatrixBlock(2, 2, new double[] {_numRows, sumIndices, sumIndices, sumSquaredIndices});
+ MatrixBlock coefficientMatrixLhs = DataConverter.convertToMatrixBlock(lhsLF._coefficents);
+ MatrixBlock coefficientMatrixRhs = DataConverter.convertToMatrixBlock(_coefficents);
+
+ coefficientMatrixLhs = LibMatrixReorg.transposeInPlace(coefficientMatrixLhs,
+ InfrastructureAnalyzer.getLocalParallelism());
+
+ // We simply compute a matrix multiplication chain in coefficient space, i.e.,
+ // t(L) %*% R = t(coeff(L)) %*% W %*% coeff(R)
+ // where W is a weight matrix capturing the size of the shared dimension (weightMatrix above)
+ // and coeff(X) denotes the 2 x n matrix of the m x n matrix X.
+ MatrixBlock tmp = new MatrixBlock(lhs.getNumCols(), 2, false);
+ LibMatrixMult.matrixMult(coefficientMatrixLhs, weightMatrix, tmp);
+ LibMatrixMult.matrixMult(tmp, coefficientMatrixRhs, tmpRet);
+ } else if(lhs instanceof APreAgg) {
+ // TODO: implement
+ throw new NotImplementedException();
+ } else {
+ throw new NotImplementedException();
+ }
+
+ final double[] resV = result.getDenseBlockValues();
+ if(tmpRet.isEmpty())
+ return;
+ else if(tmpRet.isInSparseFormat()) {
+ SparseBlock sb = tmpRet.getSparseBlock();
+ for(int row = 0; row < lhs._colIndexes.length; row++) {
+ if(sb.isEmpty(row))
+ continue;
+ final int apos = sb.pos(row);
+ final int alen = sb.size(row) + apos;
+ final int[] aix = sb.indexes(row);
+ final double[] avals = sb.values(row);
+ final int offRes = lhs._colIndexes[row] * result.getNumColumns();
+ for(int col = apos; col < alen; col++)
+ resV[offRes + _colIndexes[aix[col]]] += avals[col];
+ }
+ }
+ else {
+ double[] tmpRetV = tmpRet.getDenseBlockValues();
+ for(int row = 0; row < lhs.getNumCols(); row++) {
+ final int offRes = lhs._colIndexes[row] * result.getNumColumns();
+ final int offTmp = row * getNumCols();
+ for(int col = 0; col < getNumCols(); col++) {
+ resV[offRes + _colIndexes[col]] += tmpRetV[offTmp + col];
+ }
+ }
+ }
+ }
+
+ @Override
+ public void tsmmAColGroup(AColGroup other, MatrixBlock result) {
+ throw new DMLCompressionException("Should not be called");
+ }
+
+ @Override
+ protected AColGroup sliceSingleColumn(int idx) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected AColGroup sliceMultiColumns(int idStart, int idEnd, int[] outputCols) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup copy() {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public boolean containsValue(double pattern) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public long getNumberNonZeros(int nRows) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup replace(double pattern, double replace) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public void readFields(DataInput in) throws IOException {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public void write(DataOutput out) throws IOException {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public long getExactSizeOnDisk() {
+ long ret = super.getExactSizeOnDisk();
+ ret += _coefficents[0].length * _coefficents.length * 8L;
+ ret += 4L; // _numRows
+ return ret;
+ }
+
+ @Override
+ protected void computeProduct(double[] c, int nRows) {
+ c[0] = 1;
Review Comment:
do not set it to 1, since you have to consider the input c as already allocated correctly.
Instead you can add an early abort `if 0 return`
##########
src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupLinearFunctional.java:
##########
@@ -0,0 +1,516 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.sysds.runtime.compress.colgroup;
+
+import org.apache.commons.lang.NotImplementedException;
+import org.apache.sysds.runtime.compress.DMLCompressionException;
+import org.apache.sysds.runtime.compress.cost.ComputationCostEstimator;
+import org.apache.sysds.runtime.compress.utils.Util;
+import org.apache.sysds.runtime.controlprogram.parfor.stat.InfrastructureAnalyzer;
+import org.apache.sysds.runtime.data.DenseBlock;
+import org.apache.sysds.runtime.data.SparseBlock;
+import org.apache.sysds.runtime.functionobjects.Builtin;
+import org.apache.sysds.runtime.instructions.cp.CM_COV_Object;
+import org.apache.sysds.runtime.matrix.data.LibMatrixMult;
+import org.apache.sysds.runtime.matrix.data.LibMatrixReorg;
+import org.apache.sysds.runtime.matrix.data.MatrixBlock;
+import org.apache.sysds.runtime.matrix.operators.BinaryOperator;
+import org.apache.sysds.runtime.matrix.operators.CMOperator;
+import org.apache.sysds.runtime.matrix.operators.ScalarOperator;
+import org.apache.sysds.runtime.matrix.operators.UnaryOperator;
+import org.apache.sysds.runtime.util.DataConverter;
+
+import java.io.DataInput;
+import java.io.DataOutput;
+import java.io.IOException;
+import java.util.Arrays;
+
+public class ColGroupLinearFunctional extends AColGroupCompressed {
+
+ private static final long serialVersionUID = -2811822570758221975L;
+
+ protected double[][] _coefficents;
+
+ protected int _numRows;
+
+ /** Constructor for serialization */
+ protected ColGroupLinearFunctional() {
+ super();
+ }
+
+ /**
+ * Constructs a Linear Functional Column Group that compresses its content using a linear functional.
+ *
+ * @param colIndices The Column indexes for the column group.
+ * @param coefficents 2D-Array where coefficients[0] is the list of intercepts and coefficients[1] the list of slopes.
+ * @param numRows Number of rows encoded within this column group.
+ */
+ private ColGroupLinearFunctional(int[] colIndices, double[][] coefficents, int numRows) {
+ super(colIndices);
+ this._coefficents = coefficents;
+ this._numRows = numRows;
+ }
+
+ /**
+ * Generate a linear functional column group.
+ *
+ * @param colIndices The specific column indexes that is contained in this column group.
+ * @param coefficents 2D-Array where coefficients[0] is the list of intercepts and coefficients[1] the list of slopes.
+ * @param numRows Number of rows encoded within this column group.
+ * @return A LinearFunctional column group.
+ */
+ public static AColGroup create(int[] colIndices, double[][] coefficents, int numRows) {
+ if(coefficents.length != 2 || colIndices.length != coefficents[0].length)
+ throw new DMLCompressionException("Invalid size of values compared to columns");
+ return new ColGroupLinearFunctional(colIndices, coefficents, numRows);
+ }
+
+
+ @Override
+ protected void computeRowMxx(double[] c, Builtin builtin, int rl, int ru, double[] preAgg) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public CompressionType getCompType() {
+ return CompressionType.LinearFunctional;
+ }
+
+ @Override
+ public ColGroupType getColGroupType() {
+ return ColGroupType.LinearFunctional;
+ }
+
+ @Override
+ public double getMin() {
+ double min = Double.POSITIVE_INFINITY;
+
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ if(slope >= 0 && (intercept + slope) < min) {
+ min = intercept + slope;
+ }
+ else if(slope < 0 && (intercept + _numRows * slope) < min) {
+ min = intercept + _numRows * slope;
+ }
+ }
+
+ return min;
+ }
+
+ @Override
+ public double getMax() {
+ double max = Double.NEGATIVE_INFINITY;
+
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ if(slope >= 0 && (intercept + _numRows * slope) > max) {
+ max = intercept + _numRows * slope;
+ }
+ else if(slope < 0 && (intercept + slope) > max) {
+ max = intercept + slope;
+ }
+ }
+
+ return max;
+ }
+
+ @Override
+ public void decompressToDenseBlock(DenseBlock db, int rl, int ru, int offR, int offC) {
+ int offT = rl + offR;
+ final int nCol = _colIndexes.length;
+ int offS = rl * nCol;
+ for(int row = rl; row < ru; row++, offT++, offS += nCol) {
+ final double[] c = db.values(offT);
+ final int off = db.pos(offT) + offC;
+ for(int j = 0; j < nCol; j++)
+ c[off + _colIndexes[j]] += getIdx(row, j);
+ }
+ }
+
+ @Override
+ public void decompressToSparseBlock(SparseBlock ret, int rl, int ru, int offR, int offC) {
+ final int nCol = _colIndexes.length;
+ for(int i = rl, offT = rl + offR; i < ru; i++, offT++) {
+ for(int j = 0; j < nCol; j++)
+ ret.append(offT, _colIndexes[j] + offC, getIdx(i, j));
+ }
+ }
+
+ @Override
+ public double getIdx(int r, int colIdx) {
+ return _coefficents[0][colIdx] + _coefficents[1][colIdx] * (r + 1);
+ }
+
+ @Override
+ public AColGroup scalarOperation(ScalarOperator op) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup unaryOperation(UnaryOperator op) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup binaryRowOpLeft(BinaryOperator op, double[] v, boolean isRowSafe) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup binaryRowOpRight(BinaryOperator op, double[] v, boolean isRowSafe) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected double computeMxx(double c, Builtin builtin) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected void computeColMxx(double[] c, Builtin builtin) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected void computeSum(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[0] += nRows * (intercept + (nRows + 1) * slope / 2);
+ }
+ }
+
+ @Override
+ public void computeColSums(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[_colIndexes[col]] += nRows * (intercept + (nRows + 1) * slope / 2);
+ }
+ }
+
+ @Override
+ protected void computeSumSq(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[0] += nRows * (Math.pow(intercept, 2) + (nRows + 1) * slope * intercept +
+ (nRows + 1) * (2 * nRows + 1) * Math.pow(slope, 2) / 6);
+ }
+ }
+
+ @Override
+ protected void computeColSumsSq(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[_colIndexes[col]] += nRows * (Math.pow(intercept, 2) + (nRows + 1) * slope * intercept +
+ (nRows + 1) * (2 * nRows + 1) * Math.pow(slope, 2) / 6);
+ }
+ }
+
+ @Override
+ protected void computeRowSums(double[] c, int rl, int ru, double[] preAgg) {
+ double intercept_sum = 0;
+ for(double intercept : _coefficents[0])
+ intercept_sum += intercept;
+
+ double slope_sum = 0;
+ for(double slope : _coefficents[1])
+ slope_sum += slope;
+
+ for(int rix = rl; rix < ru; rix++)
+ c[rix] += intercept_sum + slope_sum * (rix + 1);
+ }
+
+ @Override
+ public int getNumValues() {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup rightMultByMatrix(MatrixBlock right) {
+ final int nColR = right.getNumColumns();
+ final int[] outputCols = Util.genColsIndices(nColR);
+
+ MatrixBlock result = new MatrixBlock(_numRows, nColR, false);
+ for(int j = 0; j < nColR; j++) {
+ double bias_accum = 0.0;
+ double slope_accum = 0.0;
+
+ for(int c = 0; c < _colIndexes.length; c++) {
+ bias_accum += right.getValue(_colIndexes[c], j) * _coefficents[0][c];
+ slope_accum += right.getValue(_colIndexes[c], j) * _coefficents[1][c];
+ }
+
+ for(int r = 0; r < _numRows; r++) {
+ result.setValue(r, j, bias_accum + (r+1) * slope_accum);
+ }
+ }
+
+ // returns an uncompressed ColGroup
+ return ColGroupUncompressed.create(result, outputCols);
+ }
+
+ @Override
+ public void tsmm(double[] ret, int numColumns, int nRows) {
+ // runs in O(tCol^2) since dot-products take O(1) time to compute when both vectors are linearly compressed
+ final int tCol = _colIndexes.length;
+
+ final double sumIndices = nRows * (nRows + 1)/2.0;
+ final double sumSquaredIndices = nRows * (nRows + 1) * (2*nRows + 1)/6.0;
+ for(int row = 0, offTmp = 0; row < tCol; row++, offTmp += tCol) {
+ final double alpha1 = nRows * _coefficents[0][row] + sumIndices * _coefficents[1][row];
+ final double alpha2 = sumIndices * _coefficents[0][row] + sumSquaredIndices * _coefficents[1][row];
+ final int offRet = _colIndexes[row] * numColumns;
+ for(int col = row; col < tCol; col++) {
+ ret[offRet + _colIndexes[col]] += alpha1 * _coefficents[0][col] + alpha2 * _coefficents[1][col];
+ }
+ }
+ }
+
+ @Override
+ public void leftMultByMatrixNoPreAgg(MatrixBlock matrix, MatrixBlock result, int rl, int ru, int cl, int cu) {
+ throw new DMLCompressionException("This method should never be called");
+ }
+
+ @Override
+ public void leftMultByAColGroup(AColGroup lhs, MatrixBlock result) {
+ if(lhs instanceof ColGroupEmpty) {
+ return;
+ }
+
+ MatrixBlock tmpRet = new MatrixBlock(lhs.getNumCols(), _colIndexes.length, 0);
+
+ if(lhs instanceof ColGroupUncompressed) {
+ ColGroupUncompressed lhsUC = (ColGroupUncompressed) lhs;
+ int numRowsLeft = lhsUC.getData().getNumRows();
+
+ double[] colSumsAndWeightedColSums = new double[2 * lhs.getNumCols()];
+ for(int j = 0, offTmp = 0; j < lhs.getNumCols(); j++, offTmp += 2) {
+ for(int i = 0; i < numRowsLeft; i++) {
+ colSumsAndWeightedColSums[offTmp] += lhs.getIdx(i, j);
+ colSumsAndWeightedColSums[offTmp + 1] += (i+1) * lhs.getIdx(i, j);
+ }
+ }
+
+ MatrixBlock sumMatrix = new MatrixBlock(lhs.getNumCols(), 2, colSumsAndWeightedColSums);
+ MatrixBlock coefficientMatrix = DataConverter.convertToMatrixBlock(_coefficents);
+
+ LibMatrixMult.matrixMult(sumMatrix, coefficientMatrix, tmpRet);
+ } else if(lhs instanceof ColGroupLinearFunctional) {
+ ColGroupLinearFunctional lhsLF = (ColGroupLinearFunctional) lhs;
+
+ final double sumIndices = _numRows * (_numRows + 1)/2.0;
+ final double sumSquaredIndices = _numRows * (_numRows + 1) * (2*_numRows + 1)/6.0;
+
+ MatrixBlock weightMatrix = new MatrixBlock(2, 2, new double[] {_numRows, sumIndices, sumIndices, sumSquaredIndices});
+ MatrixBlock coefficientMatrixLhs = DataConverter.convertToMatrixBlock(lhsLF._coefficents);
+ MatrixBlock coefficientMatrixRhs = DataConverter.convertToMatrixBlock(_coefficents);
+
+ coefficientMatrixLhs = LibMatrixReorg.transposeInPlace(coefficientMatrixLhs,
+ InfrastructureAnalyzer.getLocalParallelism());
+
+ // We simply compute a matrix multiplication chain in coefficient space, i.e.,
+ // t(L) %*% R = t(coeff(L)) %*% W %*% coeff(R)
+ // where W is a weight matrix capturing the size of the shared dimension (weightMatrix above)
+ // and coeff(X) denotes the 2 x n matrix of the m x n matrix X.
+ MatrixBlock tmp = new MatrixBlock(lhs.getNumCols(), 2, false);
+ LibMatrixMult.matrixMult(coefficientMatrixLhs, weightMatrix, tmp);
+ LibMatrixMult.matrixMult(tmp, coefficientMatrixRhs, tmpRet);
+ } else if(lhs instanceof APreAgg) {
+ // TODO: implement
+ throw new NotImplementedException();
+ } else {
+ throw new NotImplementedException();
+ }
+
+ final double[] resV = result.getDenseBlockValues();
+ if(tmpRet.isEmpty())
+ return;
+ else if(tmpRet.isInSparseFormat()) {
+ SparseBlock sb = tmpRet.getSparseBlock();
+ for(int row = 0; row < lhs._colIndexes.length; row++) {
+ if(sb.isEmpty(row))
+ continue;
+ final int apos = sb.pos(row);
+ final int alen = sb.size(row) + apos;
+ final int[] aix = sb.indexes(row);
+ final double[] avals = sb.values(row);
+ final int offRes = lhs._colIndexes[row] * result.getNumColumns();
+ for(int col = apos; col < alen; col++)
+ resV[offRes + _colIndexes[aix[col]]] += avals[col];
+ }
+ }
+ else {
+ double[] tmpRetV = tmpRet.getDenseBlockValues();
+ for(int row = 0; row < lhs.getNumCols(); row++) {
+ final int offRes = lhs._colIndexes[row] * result.getNumColumns();
+ final int offTmp = row * getNumCols();
+ for(int col = 0; col < getNumCols(); col++) {
+ resV[offRes + _colIndexes[col]] += tmpRetV[offTmp + col];
+ }
+ }
+ }
+ }
+
+ @Override
+ public void tsmmAColGroup(AColGroup other, MatrixBlock result) {
+ throw new DMLCompressionException("Should not be called");
+ }
+
+ @Override
+ protected AColGroup sliceSingleColumn(int idx) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected AColGroup sliceMultiColumns(int idStart, int idEnd, int[] outputCols) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup copy() {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public boolean containsValue(double pattern) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public long getNumberNonZeros(int nRows) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup replace(double pattern, double replace) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public void readFields(DataInput in) throws IOException {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public void write(DataOutput out) throws IOException {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public long getExactSizeOnDisk() {
+ long ret = super.getExactSizeOnDisk();
+ ret += _coefficents[0].length * _coefficents.length * 8L;
+ ret += 4L; // _numRows
+ return ret;
+ }
+
+ @Override
+ protected void computeProduct(double[] c, int nRows) {
+ c[0] = 1;
+ for(int colIndex : _colIndexes) {
+ double intercept = _coefficents[0][colIndex];
+ double slope = _coefficents[1][colIndex];
+ for(int i = 0; i < nRows; i++) {
+ c[0] *= intercept + slope * (i + 1);
+ }
+ }
+ }
+
+ @Override
+ protected void computeRowProduct(double[] c, int rl, int ru, double[] preAgg) {
+ for(int rix = rl; rix < ru; rix++) {
+ c[rix] = 1;
+ for(int colIndex : _colIndexes) {
+ double intercept = _coefficents[0][colIndex];
+ double slope = _coefficents[1][colIndex];
+ c[rix] *= intercept + slope * (rix + 1);
+ }
+ }
+ }
+
+ @Override
+ protected void computeColProduct(double[] c, int nRows) {
+ for(int colIndex : _colIndexes) {
+ c[colIndex] = 1;
+ double intercept = _coefficents[0][colIndex];
+ double slope = _coefficents[1][colIndex];
+ for(int i = 0; i < nRows; i++) {
+ c[colIndex] *= intercept + slope * (i + 1);
+ }
+ }
+ }
+
+ @Override
+ protected double[] preAggSumRows() {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected double[] preAggSumSqRows() {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected double[] preAggProductRows() {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected double[] preAggBuiltinRows(Builtin builtin) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public long estimateInMemorySize() {
+ return ColGroupSizes.estimateInMemorySizeLinearFunctional(getNumCols());
+ }
+
+ @Override
+ public CM_COV_Object centralMoment(CMOperator op, int nRows) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup rexpandCols(int max, boolean ignore, boolean cast, int nRows) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public double getCost(ComputationCostEstimator e, int nRows) {
+ final int nCols = getNumCols();
+ // We store 2 tuples in this column group, namely intercepts and slopes
+ return e.getCost(nRows, nRows, nCols, 2, 1.0);
Review Comment:
this is going to be tricky to calculate, since this does not correctly reflect the calculation.
i suggest you add a
`LOG.warn("Not precise cost calculation for LinearFunctional ColGroup");`
##########
src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupLinearFunctional.java:
##########
@@ -0,0 +1,516 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.sysds.runtime.compress.colgroup;
+
+import org.apache.commons.lang.NotImplementedException;
+import org.apache.sysds.runtime.compress.DMLCompressionException;
+import org.apache.sysds.runtime.compress.cost.ComputationCostEstimator;
+import org.apache.sysds.runtime.compress.utils.Util;
+import org.apache.sysds.runtime.controlprogram.parfor.stat.InfrastructureAnalyzer;
+import org.apache.sysds.runtime.data.DenseBlock;
+import org.apache.sysds.runtime.data.SparseBlock;
+import org.apache.sysds.runtime.functionobjects.Builtin;
+import org.apache.sysds.runtime.instructions.cp.CM_COV_Object;
+import org.apache.sysds.runtime.matrix.data.LibMatrixMult;
+import org.apache.sysds.runtime.matrix.data.LibMatrixReorg;
+import org.apache.sysds.runtime.matrix.data.MatrixBlock;
+import org.apache.sysds.runtime.matrix.operators.BinaryOperator;
+import org.apache.sysds.runtime.matrix.operators.CMOperator;
+import org.apache.sysds.runtime.matrix.operators.ScalarOperator;
+import org.apache.sysds.runtime.matrix.operators.UnaryOperator;
+import org.apache.sysds.runtime.util.DataConverter;
+
+import java.io.DataInput;
+import java.io.DataOutput;
+import java.io.IOException;
+import java.util.Arrays;
+
+public class ColGroupLinearFunctional extends AColGroupCompressed {
+
+ private static final long serialVersionUID = -2811822570758221975L;
+
+ protected double[][] _coefficents;
+
+ protected int _numRows;
+
+ /** Constructor for serialization */
+ protected ColGroupLinearFunctional() {
+ super();
+ }
+
+ /**
+ * Constructs a Linear Functional Column Group that compresses its content using a linear functional.
+ *
+ * @param colIndices The Column indexes for the column group.
+ * @param coefficents 2D-Array where coefficients[0] is the list of intercepts and coefficients[1] the list of slopes.
+ * @param numRows Number of rows encoded within this column group.
+ */
+ private ColGroupLinearFunctional(int[] colIndices, double[][] coefficents, int numRows) {
+ super(colIndices);
+ this._coefficents = coefficents;
+ this._numRows = numRows;
+ }
+
+ /**
+ * Generate a linear functional column group.
+ *
+ * @param colIndices The specific column indexes that is contained in this column group.
+ * @param coefficents 2D-Array where coefficients[0] is the list of intercepts and coefficients[1] the list of slopes.
+ * @param numRows Number of rows encoded within this column group.
+ * @return A LinearFunctional column group.
+ */
+ public static AColGroup create(int[] colIndices, double[][] coefficents, int numRows) {
+ if(coefficents.length != 2 || colIndices.length != coefficents[0].length)
+ throw new DMLCompressionException("Invalid size of values compared to columns");
+ return new ColGroupLinearFunctional(colIndices, coefficents, numRows);
+ }
+
+
+ @Override
+ protected void computeRowMxx(double[] c, Builtin builtin, int rl, int ru, double[] preAgg) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public CompressionType getCompType() {
+ return CompressionType.LinearFunctional;
+ }
+
+ @Override
+ public ColGroupType getColGroupType() {
+ return ColGroupType.LinearFunctional;
+ }
+
+ @Override
+ public double getMin() {
+ double min = Double.POSITIVE_INFINITY;
+
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ if(slope >= 0 && (intercept + slope) < min) {
+ min = intercept + slope;
+ }
+ else if(slope < 0 && (intercept + _numRows * slope) < min) {
+ min = intercept + _numRows * slope;
+ }
+ }
+
+ return min;
+ }
+
+ @Override
+ public double getMax() {
+ double max = Double.NEGATIVE_INFINITY;
+
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ if(slope >= 0 && (intercept + _numRows * slope) > max) {
+ max = intercept + _numRows * slope;
+ }
+ else if(slope < 0 && (intercept + slope) > max) {
+ max = intercept + slope;
+ }
+ }
+
+ return max;
+ }
+
+ @Override
+ public void decompressToDenseBlock(DenseBlock db, int rl, int ru, int offR, int offC) {
+ int offT = rl + offR;
+ final int nCol = _colIndexes.length;
+ int offS = rl * nCol;
+ for(int row = rl; row < ru; row++, offT++, offS += nCol) {
+ final double[] c = db.values(offT);
+ final int off = db.pos(offT) + offC;
+ for(int j = 0; j < nCol; j++)
+ c[off + _colIndexes[j]] += getIdx(row, j);
+ }
+ }
+
+ @Override
+ public void decompressToSparseBlock(SparseBlock ret, int rl, int ru, int offR, int offC) {
+ final int nCol = _colIndexes.length;
+ for(int i = rl, offT = rl + offR; i < ru; i++, offT++) {
+ for(int j = 0; j < nCol; j++)
+ ret.append(offT, _colIndexes[j] + offC, getIdx(i, j));
+ }
+ }
+
+ @Override
+ public double getIdx(int r, int colIdx) {
+ return _coefficents[0][colIdx] + _coefficents[1][colIdx] * (r + 1);
+ }
+
+ @Override
+ public AColGroup scalarOperation(ScalarOperator op) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup unaryOperation(UnaryOperator op) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup binaryRowOpLeft(BinaryOperator op, double[] v, boolean isRowSafe) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup binaryRowOpRight(BinaryOperator op, double[] v, boolean isRowSafe) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected double computeMxx(double c, Builtin builtin) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected void computeColMxx(double[] c, Builtin builtin) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected void computeSum(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[0] += nRows * (intercept + (nRows + 1) * slope / 2);
+ }
+ }
+
+ @Override
+ public void computeColSums(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[_colIndexes[col]] += nRows * (intercept + (nRows + 1) * slope / 2);
+ }
+ }
+
+ @Override
+ protected void computeSumSq(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[0] += nRows * (Math.pow(intercept, 2) + (nRows + 1) * slope * intercept +
+ (nRows + 1) * (2 * nRows + 1) * Math.pow(slope, 2) / 6);
+ }
+ }
+
+ @Override
+ protected void computeColSumsSq(double[] c, int nRows) {
+ for(int col = 0; col < getNumCols(); col++) {
+ double intercept = _coefficents[0][col];
+ double slope = _coefficents[1][col];
+ c[_colIndexes[col]] += nRows * (Math.pow(intercept, 2) + (nRows + 1) * slope * intercept +
+ (nRows + 1) * (2 * nRows + 1) * Math.pow(slope, 2) / 6);
+ }
+ }
+
+ @Override
+ protected void computeRowSums(double[] c, int rl, int ru, double[] preAgg) {
+ double intercept_sum = 0;
+ for(double intercept : _coefficents[0])
+ intercept_sum += intercept;
+
+ double slope_sum = 0;
+ for(double slope : _coefficents[1])
+ slope_sum += slope;
+
+ for(int rix = rl; rix < ru; rix++)
+ c[rix] += intercept_sum + slope_sum * (rix + 1);
+ }
+
+ @Override
+ public int getNumValues() {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup rightMultByMatrix(MatrixBlock right) {
+ final int nColR = right.getNumColumns();
+ final int[] outputCols = Util.genColsIndices(nColR);
+
+ MatrixBlock result = new MatrixBlock(_numRows, nColR, false);
+ for(int j = 0; j < nColR; j++) {
+ double bias_accum = 0.0;
+ double slope_accum = 0.0;
+
+ for(int c = 0; c < _colIndexes.length; c++) {
+ bias_accum += right.getValue(_colIndexes[c], j) * _coefficents[0][c];
+ slope_accum += right.getValue(_colIndexes[c], j) * _coefficents[1][c];
+ }
+
+ for(int r = 0; r < _numRows; r++) {
+ result.setValue(r, j, bias_accum + (r+1) * slope_accum);
+ }
+ }
+
+ // returns an uncompressed ColGroup
+ return ColGroupUncompressed.create(result, outputCols);
+ }
+
+ @Override
+ public void tsmm(double[] ret, int numColumns, int nRows) {
+ // runs in O(tCol^2) since dot-products take O(1) time to compute when both vectors are linearly compressed
+ final int tCol = _colIndexes.length;
+
+ final double sumIndices = nRows * (nRows + 1)/2.0;
+ final double sumSquaredIndices = nRows * (nRows + 1) * (2*nRows + 1)/6.0;
+ for(int row = 0, offTmp = 0; row < tCol; row++, offTmp += tCol) {
+ final double alpha1 = nRows * _coefficents[0][row] + sumIndices * _coefficents[1][row];
+ final double alpha2 = sumIndices * _coefficents[0][row] + sumSquaredIndices * _coefficents[1][row];
+ final int offRet = _colIndexes[row] * numColumns;
+ for(int col = row; col < tCol; col++) {
+ ret[offRet + _colIndexes[col]] += alpha1 * _coefficents[0][col] + alpha2 * _coefficents[1][col];
+ }
+ }
+ }
+
+ @Override
+ public void leftMultByMatrixNoPreAgg(MatrixBlock matrix, MatrixBlock result, int rl, int ru, int cl, int cu) {
+ throw new DMLCompressionException("This method should never be called");
+ }
+
+ @Override
+ public void leftMultByAColGroup(AColGroup lhs, MatrixBlock result) {
+ if(lhs instanceof ColGroupEmpty) {
+ return;
+ }
+
+ MatrixBlock tmpRet = new MatrixBlock(lhs.getNumCols(), _colIndexes.length, 0);
+
+ if(lhs instanceof ColGroupUncompressed) {
+ ColGroupUncompressed lhsUC = (ColGroupUncompressed) lhs;
+ int numRowsLeft = lhsUC.getData().getNumRows();
+
+ double[] colSumsAndWeightedColSums = new double[2 * lhs.getNumCols()];
+ for(int j = 0, offTmp = 0; j < lhs.getNumCols(); j++, offTmp += 2) {
+ for(int i = 0; i < numRowsLeft; i++) {
+ colSumsAndWeightedColSums[offTmp] += lhs.getIdx(i, j);
+ colSumsAndWeightedColSums[offTmp + 1] += (i+1) * lhs.getIdx(i, j);
+ }
+ }
+
+ MatrixBlock sumMatrix = new MatrixBlock(lhs.getNumCols(), 2, colSumsAndWeightedColSums);
+ MatrixBlock coefficientMatrix = DataConverter.convertToMatrixBlock(_coefficents);
+
+ LibMatrixMult.matrixMult(sumMatrix, coefficientMatrix, tmpRet);
+ } else if(lhs instanceof ColGroupLinearFunctional) {
+ ColGroupLinearFunctional lhsLF = (ColGroupLinearFunctional) lhs;
+
+ final double sumIndices = _numRows * (_numRows + 1)/2.0;
+ final double sumSquaredIndices = _numRows * (_numRows + 1) * (2*_numRows + 1)/6.0;
+
+ MatrixBlock weightMatrix = new MatrixBlock(2, 2, new double[] {_numRows, sumIndices, sumIndices, sumSquaredIndices});
+ MatrixBlock coefficientMatrixLhs = DataConverter.convertToMatrixBlock(lhsLF._coefficents);
+ MatrixBlock coefficientMatrixRhs = DataConverter.convertToMatrixBlock(_coefficents);
+
+ coefficientMatrixLhs = LibMatrixReorg.transposeInPlace(coefficientMatrixLhs,
+ InfrastructureAnalyzer.getLocalParallelism());
+
+ // We simply compute a matrix multiplication chain in coefficient space, i.e.,
+ // t(L) %*% R = t(coeff(L)) %*% W %*% coeff(R)
+ // where W is a weight matrix capturing the size of the shared dimension (weightMatrix above)
+ // and coeff(X) denotes the 2 x n matrix of the m x n matrix X.
+ MatrixBlock tmp = new MatrixBlock(lhs.getNumCols(), 2, false);
+ LibMatrixMult.matrixMult(coefficientMatrixLhs, weightMatrix, tmp);
+ LibMatrixMult.matrixMult(tmp, coefficientMatrixRhs, tmpRet);
+ } else if(lhs instanceof APreAgg) {
+ // TODO: implement
+ throw new NotImplementedException();
+ } else {
+ throw new NotImplementedException();
+ }
+
+ final double[] resV = result.getDenseBlockValues();
+ if(tmpRet.isEmpty())
+ return;
+ else if(tmpRet.isInSparseFormat()) {
+ SparseBlock sb = tmpRet.getSparseBlock();
+ for(int row = 0; row < lhs._colIndexes.length; row++) {
+ if(sb.isEmpty(row))
+ continue;
+ final int apos = sb.pos(row);
+ final int alen = sb.size(row) + apos;
+ final int[] aix = sb.indexes(row);
+ final double[] avals = sb.values(row);
+ final int offRes = lhs._colIndexes[row] * result.getNumColumns();
+ for(int col = apos; col < alen; col++)
+ resV[offRes + _colIndexes[aix[col]]] += avals[col];
+ }
+ }
+ else {
+ double[] tmpRetV = tmpRet.getDenseBlockValues();
+ for(int row = 0; row < lhs.getNumCols(); row++) {
+ final int offRes = lhs._colIndexes[row] * result.getNumColumns();
+ final int offTmp = row * getNumCols();
+ for(int col = 0; col < getNumCols(); col++) {
+ resV[offRes + _colIndexes[col]] += tmpRetV[offTmp + col];
+ }
+ }
+ }
+ }
+
+ @Override
+ public void tsmmAColGroup(AColGroup other, MatrixBlock result) {
+ throw new DMLCompressionException("Should not be called");
+ }
+
+ @Override
+ protected AColGroup sliceSingleColumn(int idx) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ protected AColGroup sliceMultiColumns(int idStart, int idEnd, int[] outputCols) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup copy() {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public boolean containsValue(double pattern) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public long getNumberNonZeros(int nRows) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public AColGroup replace(double pattern, double replace) {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public void readFields(DataInput in) throws IOException {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public void write(DataOutput out) throws IOException {
+ throw new NotImplementedException();
+ }
+
+ @Override
+ public long getExactSizeOnDisk() {
+ long ret = super.getExactSizeOnDisk();
+ ret += _coefficents[0].length * _coefficents.length * 8L;
+ ret += 4L; // _numRows
+ return ret;
+ }
+
+ @Override
+ protected void computeProduct(double[] c, int nRows) {
+ c[0] = 1;
+ for(int colIndex : _colIndexes) {
+ double intercept = _coefficents[0][colIndex];
+ double slope = _coefficents[1][colIndex];
+ for(int i = 0; i < nRows; i++) {
+ c[0] *= intercept + slope * (i + 1);
+ }
+ }
+ }
+
+ @Override
+ protected void computeRowProduct(double[] c, int rl, int ru, double[] preAgg) {
+ for(int rix = rl; rix < ru; rix++) {
+ c[rix] = 1;
Review Comment:
similar here. don't set it to 1
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@systemds.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [systemds] Baunsgaard commented on pull request #1634: [SYSTEMDS-2830] Functional Compression
Posted by GitBox <gi...@apache.org>.
Baunsgaard commented on PR #1634:
URL: https://github.com/apache/systemds/pull/1634#issuecomment-1164498351
Thansk for the PR! and addressing my comments!
I will take it from here.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@systemds.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org