Vector vs Arrays

[Vadim]

I am trying to figure out what should I use for LU decomposition algorithm: vectors or arrays. I think the initial choice is very important.

A vector is a dynamic array designed to hold objects of any type (which we do not need in the algorithm), and capable of growing and shrinking as needed (which is advantage).

Algorithm using arrays are running faster than one using vectors (which is a big advantage).

What do you think about this topic? What did student who already took Linear Algebra use?

-V-

 

[Jacob]

I would say that flexibility and readability of your code is a much bigger advantage than the runtime performance, at this stage of the game. Fine-tuning performance comes later, the priority now is to be able to understand the code and verify that it produces a correct result.

A quote from Don Knuth on the subject: "We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%."

Found here: Optimization (computer science - Wikipedia, the free encyclopedia)

 

[SteveTownsend]

I am trying to figure out what should I use for LU decomposition algorithm: vectors or arrays. I think the initial choice is very important.

A vector is a dynamic array designed to hold objects of any type (which we do not need in the algorithm), and capable of growing and shrinking as needed (which is advantage).

Algorithm using arrays are running faster than one using vectors (which is a big advantage).

What do you think about this topic? What did student who already took Linear Algebra use?

-V-

In pragmatic terms, I'd say that the quickest way to write working code is to use plain old arrays of double Try to balance ease of implementation with the knowledge that you are going to be living with this code until Xmas. You don't want to have to do a rewrite to support 5x5 matrices because you initially assumed 3x3, for example.

Using vector might make sense longer term esp. if you are very familiar with STL - you don't have to worry about bounds checking so much as long as you handle exceptions cleanly. Using arrays will make optimization for sparse matrices harder (e.g upper/ lower triangular, the identity matrix) but who cares about this at this point?

In the ideal world (ie. not under time pressure for weekend homework, or delivery of working code to your manager) it is possible to write your code such that the complexity involved in replacing a vector with an array or vice versa is not so complex. For example, when you need to access an entry (i,j) do it via "thin" accessor APIs eg.

double Matrix::getEntry(unsigned int i, unsigned int j)
{
// check bounds are valid before you do this
return data[i][j];  
}
 
void Matrix::setEntry(const unsigned int i, const  unsigned int j, const double value)
{
// check bounds are valid before you do this
data[i][j] = value;
}
 
class Matrix
{
public:
 Matrix(unsigned int i, const unsigned int j)
{
// allocate the array
}
~Matrix()
{
// free the array
}
private:
double array[][];
};

(This code won't compile, this is for illustration only.)

With this approach, you just need to replace two line of code plus the declaration, initialization, and release of the data field to change this particular subset of your implementation to use a vector instead. We are encapsulating the storage mechanism within the Matrix class to make it easier to switch in another storage mechanism if the first one is not working for us.

 

[Andy Nguyen]

This question will come back every Fall when people start coding their first matrix class. There are vector and different kind of array implementations to choose from. There are con/pro in whatever you end up using but my suggestion is to stick with whatever you feel most comfortable with. If you end up picking something unfamiliar, there will come a time next few months that you may have to redo the whole thing. It happened.

I used array for the reason it's simpler to implement and expand. We did very extensive matrix class. We have vector class where you can use operator to do all operations.

Here is an example of my Matrix header that define FullMatrix. I also have Banded matrix and sparse matrix

class FullMtx
{
private:
    int ncols; // number of columns
    int nrows; // number of rows
    void CoreConst(); // Construct array only
    void CoreDest();  // Destroy the array only
    void zero();//fill matrix entries with 0's
public:
    double** Mtx; //entries of the matrix
    FullMtx(); // n:# of row, m:# of columns

    FullMtx(int n, int m); // n:# of row, m:# of columns
    // TypeOfMtx = "I" ot "i" for identity 
    // TypeOfMtx = "Z" ot "z" for zero matrix 
    FullMtx(int n, int m, char TypeOfMtx);
    FullMtx(SparseMtx& SourceSparseMtx);
    FullMtx(BandMtx& SourceBandMtx);
    FullMtx(FullMtx & SourceFullMtx); //copy constructor
    ~FullMtx()
    {    
        CoreDest();
    };
    FullMtx operator = (FullMtx& SourceFullMtx); //assignment constructor
    FullMtx operator += (FullMtx& SourceFullMtx);
    FullMtx operator -= (FullMtx& SourceFullMtx); 
    FullMtx operator *= (double dblScalar); 
    FullMtx operator + (FullMtx& SourceFullMtx); 

    FullMtx operator - (FullMtx& SourceFullMtx);
    FullMtx operator * (FullMtx& SourceFullMtx);
    Vector operator * (Vector& SourceVector); 


    void EnterEntries();
    void Transpose();
    bool isSymmetric(FullMtx& A);
    int Rows()
        {
            return(nrows);
        };
    int Cols()
        {
            return(ncols);
        }
    void ShowMarix();

};

 

[Muting]

Jacob, Steve:

Thank you for this information. I also have a question related to these things. There is a valarray class in the STL. We can easily set up the column vectors and row vectors since we can adjust the step parameter in the valarray. But it seems that people seldom talk about this. Is that becasue it lies in STL and hard to understand?

Do you use valarray when you do matrix or vector-related algorithm?

 

[Andy Nguyen]

Thank you for this information. I also have a question related to these things. There is a valarray class in the STL. We can easily set up the column vectors and row vectors since we can adjust the step parameter in the valarray. But it seems that people seldom talk about this. Is that becasue it lies in STL and hard to understand?

Do you use valarray when you do matrix or vector-related algorithm?

We discussed valarray/vector/array last year and a couple of people used valarray. I think Alain and Max used it.

The same discussion started last year here

 

[Vadim]

I thank you for posting.

All posts are very useful and insightful.

I feel more comfortable with arrays and will use them. In my point of view, vectors are not very practical and difficult to implement.

-V-

 

[bob]

I thank you for posting.

All posts are very useful and insightful.

I feel more comfortable with arrays and will use them. In my point of view, vectors are not very practical and difficult to implement.

-V-

The main advantages of containers--particularly vectors and maps--come from development speed, particularly ease of debugging. I like the dynamic memory management that comes with them, and I don't like having to write iterators or rule-of-three member functions (default constructors, copy constructors, assignment operators) myself, which you often have to with classes that wrap one or more arrays.

With that said, I do use arrays whenever pure speed of execution is the goal. But with moderately complicated code it isn't hard to wind up with memory bugs that can be devilish to find and squash.

 

[SteveTownsend]

JDo you use valarray when you do matrix or vector-related algorithm?

I don't, but I know there are people at Baruch who have done it this way.

I am prejudiced (irrationally, most likely) against valarray only because they got a bad rap in my primary STL reference book.


The C++ Standard Library: A Tutorial and Reference by Nicolai M. Josuttis (Hardcover - Aug 12, 1999)Buy new: $69.99 $47.73 48 Used & new from $35.95Get it by Monday, Aug 20 if you order in the next 9 hours and choose one-day shipping.Eligible for FREE Super Saver Shipping.

Books: See all 117 items

Vadim - I think you will learn to love std::vector as you get more familiar with them. A lot more robust and flexible than plain old arrays, and for not much performance degradation.

There are some tricks you can use to close the gap such as using vector.reserve() to preallocate the required memory space if you know in advance how big it will be. This would work in a Matrix implementation for example where you know upfront the matrix is m by n. Using vector iterators to access the members will be faster than a plain old array index access myarray. If you use vector you have instant access to a huge number of highly-tuned, well-tested STL algorithms that you would have to write yourself for C++ arrays.

Last but not least, if you are using a well-implemented STL (e.g. Visual Studio 2005 C++ Express Edition) then you get a whole bunch of error checking when you run in Debug mode that will save you tons of time puzzling over why your code crashes randomly because you have a bug that caused you to run off the end of the array.

 

[alain]

I don't, but I know there are people at Baruch who have done it this way.

I am prejudiced (irrationally, most likely) against valarray only because they got a bad rap in my primary STL reference book.

Steve,

I think I was in the same boat until I read Stroustroup's book. In his book he gives a scheleton of a Matrix class and that was what I used as starting point. The interesting thing is that valarrays are really fast for math computations and they include implementation of multiple operators over the whole structure. Also, using valarrays and slices you can create very interesting things.

I know if you read the C++ mailing lists, you will find a lot of people against valarrays and with good reasons. Sometimes, it is combersome to deal with them although I think that if you come from a very mathematical background, you should be able to understand them.

The concept of valarrays and slices came from FORTRAN and their implementations of matrixes and handling of math operations (the original LAPACK was developed in FORTRAN).

 

[Vadim]

I would like further exchange programming (and other) experience.

I tried to use vectors in they worked fine, I became like to use vectors.
That what I am doing to identify matrix 5x10:

vector<double> vectorCColumn(10);
vector<vector<double>> MatrixC(5, vectorCColumn);

I have vector in vector. I see three main advantages in such approach: function can return such structures, elements of the vector can be accessed by using MatrixC[j], I can see nice structure of the matrix while tracing and focusing on the name of the instance.

Guys, what others approaches did you implement? I am very curious :-k.

I see a couple disadvantages of my approach:
1. I cannot drag and drop MatrixC[j] to watch windows while tracing, however I can do that for arrays, for example. Does anybody experience the same?
2. Finally we need to come up with Matrix class, which is not my case right now. It would be nice if in the code I access the matrix instance’s value by Matrix[j] rather than by set and get functions. I do not think it is possible, do you?

Thank you,
-V-

 

[SteveTownsend]

Guys, what others approaches did you implement? I am very curious :-k.

I see a couple disadvantages of my approach:
1. I cannot drag and drop MatrixC[j] to watch windows while tracing, however I can do that for arrays, for example. Does anybody experience the same?
2. Finally we need to come up with Matrix class, which is not my case right now. It would be nice if in the code I access the matrix instance's value by Matrix[j] rather than by set and get functions. I do not think it is possible, do you?

I am using Boost::numerics::ublas. This is pretty advanced C++, though. I can't see the contents of my matrices in the debugger either, I think there is a way for force VC++ to output it properly but I have not tried that yet. I use cout << myMatrix to dump them as required.

1. are you using VC++? This should work OK with vectors, if so. Not sure if the indexing works in this context but you can usually see entire vectors OK. Not always so easy with Release code, use a Debug build if you need to see the contents.

2. You would have to define a full-fledged Matrix class in order to do this that holds the storage as a member. You should then be able to achieve this by defining an operator() for your matrix with two int parameters. Typically you would define two variations of this, one with const that does not allow you to alter the element in place and a second without const that supports in-place modification of the entry.

The code might look something like the below, which won't compile (writing ad hoc) but should get across the idea.

class Matrix
{
public:
Matrix(int _dim1, int _dim2) :
dim1(_dim1), 
dim2(_dim2)
{
// reserve storage for a dim1 x dim2 vector.  
// Check bounds are +ve and throw if not
}
 
double& operator()(int row, int column)
{
// Check bounds are valid first
return entries[row][column];
}
 
private:
vector<double, <vector<double> > entries;
int dim1;
int dim2;
};
 
int main (int argc, char* argv[])
{
Matrix myMatrix(5,10);
// put some data in it
 
cout << myMatrix(3,7) << endl;
}

 

[alain]

I see a couple disadvantages of my approach:
1. I cannot drag and drop MatrixC[j] to watch windows while tracing, however I can do that for arrays, for example. Does anybody experience the same?
2. Finally we need to come up with Matrix class, which is not my case right now. It would be nice if in the code I access the matrix instance's value by Matrix[j] rather than by set and get functions. I do not think it is possible, do you?

Thank you,
-V-

Vadim,

I don't know if number 1 is possible. For number 2, as long as you return a reference to the element you are trying to modify, the assignment will work. References in C++ allow variables to become lvalues.

 

[alain]

I am using Boost::numerics::ublas. This is pretty advanced C++, though. I can't see the contents of my matrices in the debugger either, I think there is a way for force VC++ to output it properly but I have not tried that yet. I use cout << myMatrix to dump them as required.

Steve, last year I tried boost and LAPACK++ after I wrote my own Matrix code. Both libraries were very good but it took me sometime to set them up. Boost was harder to setup than LAPACK++ for me maybe because I compiled the whole library from scratch using their compiler (bjam).

Eventually I end up using my own library since I knew exactly how everything worked in my code.