Click here to Skip to main content
Click here to Skip to main content
Add your own
alternative version

Tagged as

la4j - Linear Algebra for Java

, 14 Nov 2011 CPOL
Elegant and pure Java matrix library
/*
 * Copyright 2011, Vladimir Kostyukov
 * 
 * This file is part of la4j project (http://la4j.googlecode.com)
 * 
 * Licensed 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 la4j.matrix.sparse;

import java.io.IOException;
import java.io.ObjectInput;
import java.io.ObjectOutput;

import la4j.factory.Factory;
import la4j.factory.SparseFactory;
import la4j.matrix.AbstractMatrix;
import la4j.matrix.Matrix;
import la4j.vector.Vector;

public class SparseMatrix extends AbstractMatrix implements Matrix {

	private static final int MINIMUM_SIZE = 32;
	
	private static final long serialVersionUID = 1L;
	
	private double values[];
	private int columnIndices[];
	private int rowPointers[];
	
	private int nonzero;

	public SparseMatrix() {
		this(0, 0);
	}

	public SparseMatrix(int rows, int columns) {
		this(rows, columns, 0);
	}
	
	public SparseMatrix(double array[][]) {
		this(array.length, array[0].length, 0);
		
		for (int i = 0; i < rows; i++) {
			rowPointers[i] = nonzero;
			for (int j = 0; j < columns; j++) {
				if (Math.abs(array[i][j]) > EPS) {
					
					if (values.length < nonzero + 1) {
						growup();
					}
					
					values[nonzero] = array[i][j];
					columnIndices[nonzero] = j;
					nonzero++;
				}
			}
		}
		
		rowPointers[rows] = nonzero;
	}
	
	public SparseMatrix(int rows, int columns, int nonzero) {
		super(new SparseFactory());

		this.rows = rows;
		this.columns = columns;
		this.nonzero = 0;
		
		int alignedSize = Math.min(rows * columns, ((nonzero % MINIMUM_SIZE) + 1) * MINIMUM_SIZE);

		this.values = new double[alignedSize];
		this.columnIndices = new int[alignedSize];
		this.rowPointers = new int[rows + 1];
	}
	

	@Override
	public double get(int i, int j) {
		
		if (i >= rows || i < 0 || j >= columns || j < 0) throw new IndexOutOfBoundsException();

		for(int ii = rowPointers[i]; ii < rowPointers[i + 1]; ii++) {
			if (columnIndices[ii] == j) {
				return values[ii];
			}
		}
		
		return 0.0;
	}

	@Override
	public void set(int i, int j, double value) {

		if (i >= rows || i < 0 || j >= columns || j < 0) throw new IndexOutOfBoundsException();

		for(int ii = rowPointers[i]; ii < rowPointers[i + 1]; ii++) {
			if (columnIndices[ii] == j) {
				values[ii] = value;
				return;
			}
		}
		
		if (Math.abs(value) < EPS) return;
		
		if (values.length < nonzero + 1) {
			growup();
		}
		
		int position = rowPointers[i];
		while (position < rowPointers[i + 1] && j >= columnIndices[position]) position++;
		
				
		for (int k = nonzero; k > position; k--) {
			values[k] = values[k - 1];
			columnIndices[k] = columnIndices[k - 1];
		}

		values[position] = value;
		columnIndices[position] = j;
		
		for (int k = i + 1; k < rows + 1; k++) {
			rowPointers[k]++; 
		}
		
		nonzero++;
	}
	
	@Override
	public void resize(int rows, int columns) {
		
		if (rows < 0 || columns < 0) throw new IllegalArgumentException();
		
		if (this.rows == rows && this.columns == columns) return;
		
		if (this.rows >= rows && this.columns >= columns) {
			
			int position = 0;
			for (int k = 0; k < rowPointers[rows]; k++) {
				if (columns > columnIndices[k]) {
					values[position++] = values[k];				
				}
			}

			nonzero = rowPointers[rows];
			
		} else if (this.rows < rows) {
			
			int newRowPointers[] = new int[rows + 1];
			System.arraycopy(rowPointers, 0, newRowPointers, 0, rowPointers.length);
			
			for (int i = this.rows; i < rows; i++) {
				newRowPointers[i] = nonzero;
			}
			
			this.rowPointers = newRowPointers;
		}
		
		this.rows = rows;
		this.columns = columns;
	}

	@Override
	public double[][] toArray() {

		double result[][] = new double[rows][columns];

		int k = 0, i = 0;
		while (k < nonzero) {
			for (int j = rowPointers[i]; j < rowPointers[i + 1]; j++, k++) {
				result[i][columnIndices[j]] = values[j];
			}
			i++;
		}

		return result;
	}

	@Override
	public double[][] toArrayCopy() {
		return toArray();
	}

	@Override
	public void swapRows(int i, int j) {
		
		// TODO: optimize it
		
		if (i >= rows || i < 0 || j >= rows || j < 0) throw new IndexOutOfBoundsException();
		
		if (i == j) return;

		Vector ii = getRow(i);
		Vector jj = getRow(j);
		
		setRow(i, jj);
		setRow(j, ii);
	}
	
	@Override
	public void swapColumns(int i, int j) {
		
		// TODO: optimize it
		
		if (i >= columns || i < 0 || j >= columns || j < 0) throw new IndexOutOfBoundsException();
		
		if (i == j) return;
		
		Vector ii = getColumn(i);
		Vector jj = getColumn(j);
		
		setColumn(i, jj);
		setColumn(j, ii);
	}		
	
	@Override
	public int nonzero() {
		return nonzero;
	}

	@Override
	public Matrix transpose(Factory factory) {
		
		if (factory == null) throw new NullPointerException();

		Matrix result = factory.createMatrix(columns, rows);
		
		int k = 0, i = 0;
		while (k < nonzero) {
			for (int j = rowPointers[i]; j < rowPointers[i + 1]; j++, k++) {
				result.set(columnIndices[j], i, values[j]);
			}
			i++;
		}
		
		return result;
	}

	@Override
	public Vector getRow(int i) {
		
		if (i >= rows || i < 0) throw new IndexOutOfBoundsException();
		
		Vector result = factory.createVector(columns);
		
		for(int ii = rowPointers[i]; ii < rowPointers[i + 1]; ii++) {
			result.set(columnIndices[ii], values[ii]);
		}
		
		return result;
	}

	@Override
	public Vector getColumn(int i) {
		
		if (i >= columns || i < 0) throw new IndexOutOfBoundsException();
		
		Vector result = factory.createVector(rows);
		
		int k = 0, ii = 0;
		while (k < nonzero) {
			for (int jj = rowPointers[ii]; jj < rowPointers[ii + 1]; jj++, k++) {
				if (columnIndices[jj] == i) {
					result.set(ii, values[jj]);
				}
			}
			ii++;
		}
		
		return result;
	}

	@Override
	public void setColumn(int i, Vector column) {

		if (i >= columns || i < 0) throw new IndexOutOfBoundsException();

		for (int ii = 0; ii < column.length(); ii++) {
			
			int position = rowPointers[ii], limit = rowPointers[ii + 1];
			while (position < limit && columnIndices[position] < i) position++;
			
			if (Math.abs(column.get(ii)) > EPS) {

				if (columnIndices[position] != i) {

					if (values.length < nonzero + 1) {
						growup();
					}
		
					for (int k = nonzero; k > position; k--) {
						values[k] = values[k - 1];
						columnIndices[k] = columnIndices[k - 1];
					}
				} 
				
				for (int k = ii + 1; k < rows + 1; k++) {
					rowPointers[k]++; 
				}
				
				values[position] = column.get(ii);
				columnIndices[position] = i;
				nonzero++;
				
			} else if (columnIndices[position] == i && position < limit) {

				for (int k = position; k < nonzero - 1; k++) {
					values[k] = values[k + 1];
					columnIndices[k] = columnIndices[k + 1];
				}
				
				for (int k = ii + 1; k < rows + 1; k++) {
					rowPointers[k]--; 
				}
				
				nonzero--;
			}
		}
	}

	@Override
	public void setRow(int i, Vector row) {
		
		// TODO: optimize it
		
		if (i >= rows || i < 0) throw new IndexOutOfBoundsException();
		
		int position = rowPointers[i], limit = rowPointers[i + 1];
		
		rowPointers[i] = limit;
		
		for (int ii = 0; ii < row.length(); ii++) {
			
			if (Math.abs(row.get(ii)) > EPS) {
				
				if (position >= limit) {

					if (values.length < nonzero + 1) {
						growup();
					}
		
					for (int k = nonzero; k > position; k--) {
						values[k] = values[k - 1];
						columnIndices[k] = columnIndices[k - 1];
					}
					
					nonzero++;

				} else {
					
					rowPointers[i]--;

				}
				
				values[position] = row.get(ii);
				columnIndices[position] = ii;
				position++;
			}
		}
		
		if (limit > position) {
			
			nonzero -= (limit - position);

			for (int k = position; k < nonzero; k++) {
				values[k] = values[k + (limit - position)];
				columnIndices[k] = columnIndices[k + (limit - position)];
			}
			
			rowPointers[i] -= (limit - position);
		}
		
		for (int k = i + 1; k < rows + 1; k++) {
			rowPointers[k] +=  (position - limit); 
		}
	}
	
	@Override
	public void writeExternal(ObjectOutput out) throws IOException {

		out.writeInt(rows);
		out.writeInt(columns);
		out.writeInt(nonzero);
		out.writeByte(META_MARKER);
		
		int k = 0, i = 0;
		while (k < nonzero) {
			for (int j = rowPointers[i]; j < rowPointers[i + 1]; j++, k++) {
				out.writeInt(i);
				out.writeInt(columnIndices[j]);
				out.writeDouble(values[j]);
				out.writeByte(ELEMENT_MARKER);
			}
			i++;
		}
	}

	@Override
	public void readExternal(ObjectInput in) throws IOException, ClassNotFoundException {
		
		// TODO: make it works with non-sorted input
		
		rows = in.readInt();
		columns = in.readInt();
		nonzero = in.readInt();
		in.readByte();

		int alignedSize = Math.min(rows * columns, ((nonzero % MINIMUM_SIZE) + 1) * MINIMUM_SIZE);
		
		values = new double[alignedSize];
		columnIndices = new int[alignedSize];
		rowPointers = new int[rows + 1];
		
		for (int k = 0; k < nonzero; k++) {
			
			int i = in.readInt();
			
			columnIndices[k] = in.readInt();
			values[k] = in.readDouble();

			in.readByte();

			rowPointers[i + 1] = k + 1;
		}
	}
	
	@Override
	public Matrix clone() {

		SparseMatrix dolly = (SparseMatrix) super.clone();
		
		dolly.values = values.clone();
		dolly.columnIndices = columnIndices.clone();
		dolly.rowPointers = rowPointers.clone();

		return dolly;
	}
	
	private void growup() {

		int newSize = Math.min(rows * columns, (nonzero * 3) / 2 + 1);
		
		double newValues[] = new double[newSize];
		int newColumnIndices[] = new int[newSize];
		
		System.arraycopy(values, 0, newValues, 0, nonzero);
		System.arraycopy(columnIndices, 0, newColumnIndices, 0, nonzero);
		
		this.values = newValues;
		this.columnIndices = newColumnIndices;
	}
}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Vladimir Kostyukov
Software Developer Intel
Russian Federation Russian Federation
I've received a Master's Degree in Computer Science at the IT Faculty of Altai State Technical University, Russia.

Currently, I am Software Engineer at Intel Corporation.
Follow on   Twitter

| Advertise | Privacy | Terms of Use | Mobile
Web03 | 2.8.150331.1 | Last Updated 14 Nov 2011
Article Copyright 2011 by Vladimir Kostyukov
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid