You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by "Mark R. Diggory" <md...@latte.harvard.edu> on 2003/11/23 20:56:22 UTC
Fwd: [math] Contribution to math.linear - CholeskySolver
I would like to forward this to the list so that others can look at it
and comment as well. Please do try to use the Developers List as I am
not always available, others may have more experience with a particular
class or implementation in the package.
I will do an initial commit of the code into experimental, and once the
code has been deemed acceptable by the group, we can migrate the solver
into src/java and the Test into src/test.
Cheers,
-Mark
>
> Hello Mark,
>
> to extend the jakarta-math.linear-package I've
> implemented the Cholesky-algorithm.
>
> The attached Zip-file contains
> * CholeskySolver.java (the algorithm)
> * CholeskySolverTest.java (JUnit-TestCase)
> * BugfixAndSuggestions.txt (to impove RealMatrixImpl.java)
>
> If you okay this contribution, I will volunteer for
> Householder decomposition (QR), Gauss-Seidel iteration and
> Jacobi iteration. Since this will become some work, I would
> like to see a positive reaction first.
>
I think we will find theres lots of room to move forward with
implementing these algorithms. I would suggest to continue with your
approach. Much of my own interest is currently in architecture and
reusability, so we could always use a hand in algorithm development. If
we do make any architectural decisions, it may effect what you've
submitted through refactoring.
> Frankfurt a. M., 23.11.2003
> Stefan Koeberle
>
> stefan.koeberle@berata.com
I'm going to include the recommendation to RealMatrix in this email so
we can get comments from the group.
> 1. RealMatrixImpl.multiply
> Method RealMatrixImpl.multiply is broken. It can't multiply a Matrix of
> dimension n*k with a matrix of dimension k*m for k<>n<>m.
> I append a correct implementation of this method and an additional test for
> RealMatrixImplTest.multiply somewhere below.
>
Sensible. I will apply this to RealMatrix and test it.
> 2. RealMatrixImpl.getData
> Method RealMatrixImpl.getData returns a copy of the stored data. Every call
> of this method will require the allocation of a new double[][]-object and the
> corresponding copy-operation. Since it is called in RealMatrixImpl.add,
> RealMatrixImpl.subtract, ... this behaviour will wreck performance. It's
> completely unnecessary, too.
> Suggestion: RealMatrixImpl.getData should return a reference to the stored
> array. Method RealMatrixImpl.getDataRef is unnecessary and should be removed.
>
I suspect this is an area where discussions concerning encapsulation and
exposure of internal datastructures can get heated. Yes, unnecessary
copying should be avoided when performing Matrix operations.
Traditionally, we should possibly consider the usage of methods like
Object[] toArray() of the collections API as a model. Does this
publically exposed method always create a copy of the Collections
internal datastructure? Yes, infact it does:
http://java.sun.com/j2se/1.4.2/docs/api/java/util/Collection.html#toArray()
But, well documented behaviors should be made because an Object[] simply
holds references to the same Objects that are referenced in the
Collection, and not a new copy of that object. If the same concept is
applied to
public double[][] toDoubleArray()
and it actually returns a copy, changing a value at
foo.toDoubleArray()[x][y] doesn't change the double stored in the
internal double[][] as well. The primitive case can't be made
behaviorally equivalent to the Collection case.
I think we should maintain methods that return a copy and methods that
return a reference, I would recommend that methods that return a
reference be protected and used internally for processing methods like
RealMatrixImpl.subtract. your correct about the copying, simply
replacing all the getData() methods with getDataRef() methods solves
this however.
public RealMatrix subtract(RealMatrix m) throws
IllegalArgumentException {
...
*double[][] mData = m.getDataRef();*
for (int row = 0; row < rowCount; row++) {
for (int col = 0; col < columnCount; col++) {
outData[row][col] = data[row][col] - mData[row][col];
}
}
return new RealMatrixImpl(outData);
}
> 3. RealMatrixImpl.getIdentity
> Method RealMatrixImpl.getIdentity doesn't GET an internal value of RealMatrixImpl.
> It creates a new matrix and should be named "createIdentity" or "newIdentity".
> The code can be simplified. A new implementation is appended below.
>
Yes, descriptive method names should be appropriate.
> 4. RealMatrixImpl.toString
> For debugging and testing there should be an easy way to print the elements
> of the matrix. I suggest to use the toString method.
> For a possible implementation just scroll down.
>
good.
>
> public static RealMatrix newIdentity(int dimension) {
> double[][] val = new double[dimension][dimension];
> //here: All elements of val are zero. That is guaranteed by the
> //Java language specification.
> for (int i=0; i<val.length; i++)
> val[i][i] = 1.0d;
> return new RealMatrixImpl(val);
> }//newIdentity
>
>
>
> public String toString() {
> StringBuffer res = new StringBuffer();
> res.append("RealMatrixImpl{");
> for (int i=0; i<data.length; i++) {
> if (i>0) res.append(",");
> res.append("{");
> for (int j=0; j<data[0].length; j++) {
> if (j>0) res.append(",");
> res.append(data[i][j]);
> }//for
> res.append("}");
> }//for
> res.append("}");
> return res.toString();
> }//toString
>
>
>
> /**
> * Returns the result postmultiplying this by <code>m</code>.
> * @param m matrix to postmultiply by
> * @return this*m
> * @throws IllegalArgumentException
> * if columnDimension(this) != rowDimension(m)
> */
> public RealMatrix multiply(RealMatrix m) throws IllegalArgumentException {
> if (this.getColumnDimension() != m.getRowDimension()) {
> throw new IllegalArgumentException
> ("Matrices are not multiplication compatible.");
> }
> int nRows = this.getRowDimension();
> int nCols = m.getColumnDimension();
> int nSum = this.getColumnDimension();
> double[][] mData = m.getData();
> double[][] outData = new double[nRows][nCols];
> double sum = 0;
> for (int row = 0; row < nRows; row++) {
> for (int col = 0; col < nCols; col++) {
> sum = 0;
> for (int i = 0; i < nSum; i++) {
> sum += data[row][i] * mData[i][col];
> }
> outData[row][col] = sum;
> }
> }
> return new RealMatrixImpl(outData);
> }
>
>
> //Additional Test for RealMatrixImplTest.testMultiply
>
> private double[][] d3 = new double[][] {{1,2,3,4},{5,6,7,8}};
> private double[][] d4 = new double[][] {{1},{2},{3},{4}};
> private double[][] d5 = new double[][] {{30},{70}};
>
> public void testMultiply1() {
> RealMatrix m3 = new RealMatrixImpl(d3);
> RealMatrix m4 = new RealMatrixImpl(d4);
> RealMatrix m5 = new RealMatrixImpl(d5);
> assertClose("m3*m4=m5", m3.multiply(m4), m5, entryTolerance);
> }
>
>
--
Mark Diggory
Software Developer
Harvard MIT Data Center
http://www.hmdc.harvard.edu
Re: Fwd: [math] Contribution to math.linear - CholeskySolver
Posted by "Mark R. Diggory" <md...@latte.harvard.edu>.
Paul Libbrecht wrote:
> Mark R. Diggory wrote:
>
>> I suspect this is an area where discussions concerning encapsulation
>> and exposure of internal datastructures can get heated. Yes,
>> unnecessary copying should be avoided when performing Matrix operations.
>>
>> Traditionally, we should possibly consider the usage of methods like
>> Object[] toArray() of the collections API as a model. Does this
>> publically exposed method always create a copy of the Collections
>> internal datastructure? Yes, infact it does:
>>
>> http://java.sun.com/j2se/1.4.2/docs/api/java/util/Collection.html#toArray()
>>
>
>
> True for collections.
> But javax.swing.text.GapContent (which is beloved by many) uses Segments
> which is a simple way to hack into its array, and known to be such).
>
hmm, I'll take a look at it, I havn't used it before.
> I agree with the point that using this method to perform each
> computation (i.e. from the same subclass hierarchy) is a bit heavy...
>
true.
>> But, well documented behaviors should be made because an Object[] simply
>
> [...]> I think we should maintain methods that return a copy and methods
> that
>
>> return a reference, I would recommend that methods that return a
>> reference be protected and used internally for processing methods like
>> RealMatrixImpl.subtract. your correct about the copying, simply
>> replacing all the getData() methods with getDataRef() methods solves
>> this however.
>>
>> public RealMatrix subtract(RealMatrix m) throws
>> IllegalArgumentException {
>> ...
>> *double[][] mData = m.getDataRef();*
>> for (int row = 0; row < rowCount; row++) {
>> for (int col = 0; col < columnCount; col++) {
>> outData[row][col] = data[row][col] - mData[row][col];
>> }
>> }
>> return new RealMatrixImpl(outData);
>> }
>
>
> But there could be ten thousand time more "interface" based approaches!
>
> One thing for sure: a RowIterator and a ColumnIterator are needed,
> returning vectors... inner class implementations of course.
> Substraction, if it is to return a RealMatrixImpl, should then use these
> instead of accessing the whole array directly!
>
Hmm, novel, something that would just return public double next()? I
suppose it could have additional ListIterator functionality, cursoring, etc.
interface VectorIterator {
public double next();
public boolean hasNext();
public double previous();
public boolean hasPrevious();
public double current();
public int cursor();
public int size();
}
> And... I wonder wether it wouldn't make sense to provide the difference
> of two matrices as being a simple object (implementing matrix) but which
> stores nothing: simply responds the difference of its two terms
> every-time it's requested for its value.
*static RealMatrix subtract(RealMatrix arg0, RealMatrix arg1)*
RealMatrix a = ...
RealMatrix b = ...
RealMatrix c = RealMatrix.subtract(a, b);
or
class Subtract implmenets RealMatrix{
public Subtract(RealMatrix arg0, RealMatrix arg1)*
}
RealMatrix a = ...
RealMatrix b = ...
RealMatrix c = new Subtract(a, b);
or
*RealMatrix subtract(RealMatrix arg0)*
RealMatrix a = ...
RealMatrix b = ...
RealMatrix c = a.subtract(b)
seems there'd be many alternatives...
-Mark
--
Mark Diggory
Software Developer
Harvard MIT Data Center
http://osprey.hmdc.harvard.edu
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org
Re: Fwd: [math] Contribution to math.linear - CholeskySolver
Posted by Paul Libbrecht <pa...@activemath.org>.
Mark R. Diggory wrote:
> I suspect this is an area where discussions concerning encapsulation and
> exposure of internal datastructures can get heated. Yes, unnecessary
> copying should be avoided when performing Matrix operations.
>
> Traditionally, we should possibly consider the usage of methods like
> Object[] toArray() of the collections API as a model. Does this
> publically exposed method always create a copy of the Collections
> internal datastructure? Yes, infact it does:
>
> http://java.sun.com/j2se/1.4.2/docs/api/java/util/Collection.html#toArray()
True for collections.
But javax.swing.text.GapContent (which is beloved by many) uses Segments
which is a simple way to hack into its array, and known to be such).
I agree with the point that using this method to perform each
computation (i.e. from the same subclass hierarchy) is a bit heavy...
> But, well documented behaviors should be made because an Object[] simply
[...]> I think we should maintain methods that return a copy and methods
that
> return a reference, I would recommend that methods that return a
> reference be protected and used internally for processing methods like
> RealMatrixImpl.subtract. your correct about the copying, simply
> replacing all the getData() methods with getDataRef() methods solves
> this however.
>
> public RealMatrix subtract(RealMatrix m) throws
> IllegalArgumentException {
> ...
> *double[][] mData = m.getDataRef();*
> for (int row = 0; row < rowCount; row++) {
> for (int col = 0; col < columnCount; col++) {
> outData[row][col] = data[row][col] - mData[row][col];
> }
> }
> return new RealMatrixImpl(outData);
> }
But there could be ten thousand time more "interface" based approaches!
One thing for sure: a RowIterator and a ColumnIterator are needed,
returning vectors... inner class implementations of course.
Substraction, if it is to return a RealMatrixImpl, should then use these
instead of accessing the whole array directly!
And... I wonder wether it wouldn't make sense to provide the difference
of two matrices as being a simple object (implementing matrix) but which
stores nothing: simply responds the difference of its two terms
every-time it's requested for its value.
Paul
Paul
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org
Re: Fwd: [math] Contribution to math.linear - CholeskySolver
Posted by "Mark R. Diggory" <md...@latte.harvard.edu>.
To be a little clearer, I think that RealMatrix shouldn't neccessarily
be an Interface, it may be more logical to use an Abstract Class as the
basis for this. Then a RealMatrix could have both public, protected, and
private methods well defined and usable in its implementations.
public abstract class RealMatrix{
public static newInstance(double[][] values){
/* instantiates a RealMatrix of a
* generic underlying implementation
*/
}
/* nice generic implementation of subtraction
* that could be overiden in the implementing
* class. Promotes polymorphism.
*/
public RealMatrix subtract(RealMatrix m){
/*...*/
int rowCount = this.getRowDimension();
int columnCount = this.getColumnDimension();
double[][] outData = new double[rowCount][columnCount];
*double[][] mData = m.getDataRef();*
for (int row = 0; row < rowCount; row++) {
for (int col = 0; col < columnCount; col++) {
outData[row][col] = data[row][col] - mData[row][col];
}
}
*return RealMatrix.newInstance(outData);*
}
...
protected abstract double[][] getDataRef();
protected abstract double[][] getData();
...
}
I think this is really much more usefull in the long run and can be more
easily adapted to different underlying implementations in the future.
The important features are the abstract implementation of the protected
and public getData/Ref methods plus the Factory style
RealMatrix.newInstance(outData) method.
-Mark
Mark R. Diggory wrote:
> I would like to forward this to the list so that others can look at it
> and comment as well. Please do try to use the Developers List as I am
> not always available, others may have more experience with a particular
> class or implementation in the package.
>
> I will do an initial commit of the code into experimental, and once the
> code has been deemed acceptable by the group, we can migrate the solver
> into src/java and the Test into src/test.
>
> Cheers,
> -Mark
>
>>
>> Hello Mark,
>> to extend the jakarta-math.linear-package I've implemented the
>> Cholesky-algorithm.
>> The attached Zip-file contains
>> * CholeskySolver.java (the algorithm)
>> * CholeskySolverTest.java (JUnit-TestCase)
>> * BugfixAndSuggestions.txt (to impove RealMatrixImpl.java)
>>
>> If you okay this contribution, I will volunteer for
>> Householder decomposition (QR), Gauss-Seidel iteration and
>> Jacobi iteration. Since this will become some work, I would like to
>> see a positive reaction first.
>>
>
> I think we will find theres lots of room to move forward with
> implementing these algorithms. I would suggest to continue with your
> approach. Much of my own interest is currently in architecture and
> reusability, so we could always use a hand in algorithm development. If
> we do make any architectural decisions, it may effect what you've
> submitted through refactoring.
>
>> Frankfurt a. M., 23.11.2003
>> Stefan Koeberle
>>
>> stefan.koeberle@berata.com
>
>
> I'm going to include the recommendation to RealMatrix in this email so
> we can get comments from the group.
>
>> 1. RealMatrixImpl.multiply
>> Method RealMatrixImpl.multiply is broken. It can't multiply a Matrix
>> of dimension n*k with a matrix of dimension k*m for k<>n<>m. I append
>> a correct implementation of this method and an additional test for
>> RealMatrixImplTest.multiply somewhere below.
>>
>
> Sensible. I will apply this to RealMatrix and test it.
>
>> 2. RealMatrixImpl.getData
>> Method RealMatrixImpl.getData returns a copy of the stored data. Every
>> call of this method will require the allocation of a new
>> double[][]-object and the
>> corresponding copy-operation. Since it is called in RealMatrixImpl.add,
>> RealMatrixImpl.subtract, ... this behaviour will wreck performance.
>> It's completely unnecessary, too.
>> Suggestion: RealMatrixImpl.getData should return a reference to the
>> stored array. Method RealMatrixImpl.getDataRef is unnecessary and
>> should be removed.
>>
>
> I suspect this is an area where discussions concerning encapsulation and
> exposure of internal datastructures can get heated. Yes, unnecessary
> copying should be avoided when performing Matrix operations.
>
> Traditionally, we should possibly consider the usage of methods like
> Object[] toArray() of the collections API as a model. Does this
> publically exposed method always create a copy of the Collections
> internal datastructure? Yes, infact it does:
>
> http://java.sun.com/j2se/1.4.2/docs/api/java/util/Collection.html#toArray()
>
> But, well documented behaviors should be made because an Object[] simply
> holds references to the same Objects that are referenced in the
> Collection, and not a new copy of that object. If the same concept is
> applied to
>
> public double[][] toDoubleArray()
>
> and it actually returns a copy, changing a value at
> foo.toDoubleArray()[x][y] doesn't change the double stored in the
> internal double[][] as well. The primitive case can't be made
> behaviorally equivalent to the Collection case.
>
>
> I think we should maintain methods that return a copy and methods that
> return a reference, I would recommend that methods that return a
> reference be protected and used internally for processing methods like
> RealMatrixImpl.subtract. your correct about the copying, simply
> replacing all the getData() methods with getDataRef() methods solves
> this however.
>
> public RealMatrix subtract(RealMatrix m) throws
> IllegalArgumentException {
> ...
> *double[][] mData = m.getDataRef();*
> for (int row = 0; row < rowCount; row++) {
> for (int col = 0; col < columnCount; col++) {
> outData[row][col] = data[row][col] - mData[row][col];
> }
> }
> return new RealMatrixImpl(outData);
> }
>
>
>
>> 3. RealMatrixImpl.getIdentity
>> Method RealMatrixImpl.getIdentity doesn't GET an internal value of
>> RealMatrixImpl.
>> It creates a new matrix and should be named "createIdentity" or
>> "newIdentity".
>> The code can be simplified. A new implementation is appended below.
>>
>
> Yes, descriptive method names should be appropriate.
>
>
>> 4. RealMatrixImpl.toString
>> For debugging and testing there should be an easy way to print the
>> elements of the matrix. I suggest to use the toString method. For a
>> possible implementation just scroll down.
>>
>
> good.
>
>> public static RealMatrix newIdentity(int dimension) {
>> double[][] val = new double[dimension][dimension];
>> //here: All elements of val are zero. That is guaranteed
>> by the
>> //Java language specification.
>> for (int i=0; i<val.length; i++) val[i][i] = 1.0d;
>> return new RealMatrixImpl(val);
>> }//newIdentity
>>
>> public String toString() {
>> StringBuffer res = new StringBuffer();
>> res.append("RealMatrixImpl{");
>> for (int i=0; i<data.length; i++) {
>> if (i>0) res.append(",");
>> res.append("{");
>> for (int j=0; j<data[0].length; j++) {
>> if (j>0) res.append(",");
>> res.append(data[i][j]);
>> }//for
>> res.append("}");
>> }//for
>> res.append("}");
>> return res.toString();
>> }//toString
>>
>> /**
>> * Returns the result postmultiplying this by <code>m</code>.
>> * @param m matrix to postmultiply by
>> * @return this*m
>> * @throws IllegalArgumentException
>> * if columnDimension(this) != rowDimension(m)
>> */
>> public RealMatrix multiply(RealMatrix m) throws
>> IllegalArgumentException {
>> if (this.getColumnDimension() != m.getRowDimension()) {
>> throw new IllegalArgumentException
>> ("Matrices are not multiplication compatible.");
>> }
>> int nRows = this.getRowDimension();
>> int nCols = m.getColumnDimension();
>> int nSum = this.getColumnDimension();
>> double[][] mData = m.getData();
>> double[][] outData = new double[nRows][nCols];
>> double sum = 0;
>> for (int row = 0; row < nRows; row++) {
>> for (int col = 0; col < nCols; col++) {
>> sum = 0;
>> for (int i = 0; i < nSum; i++) {
>> sum += data[row][i] * mData[i][col];
>> }
>> outData[row][col] = sum;
>> }
>> }
>> return new RealMatrixImpl(outData);
>> }
>>
>>
>> //Additional Test for RealMatrixImplTest.testMultiply
>>
>> private double[][] d3 = new double[][] {{1,2,3,4},{5,6,7,8}};
>> private double[][] d4 = new double[][] {{1},{2},{3},{4}};
>> private double[][] d5 = new double[][] {{30},{70}};
>> public void testMultiply1() { RealMatrix m3 = new
>> RealMatrixImpl(d3); RealMatrix m4 = new RealMatrixImpl(d4);
>> RealMatrix m5 = new RealMatrixImpl(d5);
>> assertClose("m3*m4=m5", m3.multiply(m4), m5, entryTolerance);
>> }
>
>
>
>
>
>
> ------------------------------------------------------------------------
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
> For additional commands, e-mail: commons-dev-help@jakarta.apache.org
--
Mark Diggory
Software Developer
Harvard MIT Data Center
http://www.hmdc.harvard.edu
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org