Mutable Vector Operations

[RaffEdwardBAH]

The current API suggests that set & swap are the only mutable operations on a Vector object in la4j.

While strictly non mutable ops are certainly easy to reason about, there are performance situations in which they are prohibitive. For example, in some of my current work I would have a dense vector of 10 million+ items that is updated by sparse vectors. These would be a single object of 80 MB, and would go strait to the large object heap - causing excess memory use and GC pressure in addition to the unneeded overhead of allocating 80 MB objects on each mutation of only a handful of non zero values.

While it seems I will be able to implement my needed behavior, adding mutable methods would be a nice benefit for your library.

[vkostyukov]

Hi @RaffEdwardBAH,

That is a very good point.

The la4j library is currently on track to get an engine that is able to peform in-place/out-of-place operations. The version 0.5.0 should support this. The API's changes are minor:

// b, c - vectors
Vector a  = b.multiply(c); // standard out-of-place operation
Vector aa = b.multiply(c, LinearAlgebra.IN_PLACE); // in-place operation 

I have a bunch of issues/blog-post regarding this issue: #81, #56, this wiki page (an engine section), this blog-posts.

Thanks for mentioning the issue. I understand how it's important. And I promise you'll love the version 0.5.0 :)

[RaffEdwardBAH]

I'm glad you are working on it, but I want to comment hat your example API usage is quite confusing.

Vector aa = b.multiply(c, LinearAlgebra.IN_PLACE);

Clearly implies that aa is a new object, but your comments are implying that the method will mutate b in place so that b and a will have the same values. Does this mean aa is a second reference the the object b?

This would also make the return results inconsistent - sometimes a new object (current style) and sometimes a reference to the same (new style w/ engine).

I would encourage you to consider a different method handle for in-place operations. Not only would it be less verbose, but it would better convey the desired semantics as different from the normal multiply call.

EDIT: Pardon the close and reopen bit. I'm new to github's comment system.

[vkostyukov]

That is correct. In the example aa is actually mutated b. The thing is that you don't even need to store a result in the reference. The following statement is also correct:

b.multiply(c, LinearAlgebra.IN_PLACE);

Actually, I don't thing it's confusing. There is a clear sign - IN_PLACE that indicates that operation will be perfumed in-place rather the out-of-place. We might have duplicate all the methods with a new companions methods like multiplyInPlace(...). But that is a common practice when in-place method returns this (i.e., JAMA does it).

When you need an in-place operation, you typically have something like this:

Vector a = ...
Vector b = ..

while (...) {
  a = a.multiply(b);
}

In such cases it's clear that a.multiply(b, LinearAlgebra.IN_PLACE) is not confusing. Even more it's such natural.

But, it's true. When you have logically-piped operations, you should be careful with using IN_PLACE engine within your flow.

Anyway, it's still an opened question. I was thinking quite a lot on API and found this approach quite simple and nice. If you know a better way to express the things, please go ahed. I'm 100% open for the discussion.

[RaffEdwardBAH]

"Actually, I don't thing it's confusing. There is a clear sign - IN_PLACE that indicates that operation will be perfumed in-place rather the out-of-place."

Yes, but that is only because this is a simple operation. I do not know your plans in full, but consider taking the LU decomposition, where we decompose an input matrix into two items - L and U. IN_PLACE becomes ambiguous. Does in-place mean that the input matrix will become one of L or U? Or will a form be used such that L and U are stored in the same matrix (the input one). But then other decompositions such as QR and SVD will further complicate the meaning of "in place".

Even just extending the concept to matrix vector products becomes non obvious to me.

"If you know a better way to express the things, please go ahed. I'm 100% open for the discussion."

I already mentioned my feeling, a separately named method is more consistent and logical in my opinion.

[vkostyukov]

Right. I see your porint.

I was thinking about the in-place inversions and decompositions. And, actually, it doesn't seem to be useful. Since, there is no algorithms that can do such operations in-place. The most famous couple of SVD and EVG are good examples of algorithms w/o in-place versions. It's just impossible to perform such things in-place.

The same picture is for marix inversions.

We're in trouble with LA. There are no efficient in-place algorithms. Almost all the operations required the O(n^3) time and the same amount of place. Which is not scalable at all. Moreover, the simple iteration over matrix elements is O(n^2), which is also not scalable (just drwa the line). We have to deal with it. And the best things we can do is (a) provide an efficient in-place opertaions for base things (b) work with sparse entries as fast as possible. These two ideas will allow to implement out-of-place decopmositions (internally) in a most efficient way.

[RaffEdwardBAH]

The most famous couple of SVD and EVG are good examples of algorithms w/o in-place versions.

This is part of why I don't like the proposed "engine". A thin SVD can actually be done in place if it is thin enough relative to the input size. There are also some decompositions which permit easy / simple out of core algorithms that use O(1) additional memory.

Almost all the operations required the O(n^3) time and the same amount of place. Which is not scalable at all. Moreover, the simple iteration over matrix elements is O(n^2)

Depends on how you look at it. If we limit ourselves to only square matrices, we can say that we have n^2 = k elements we are operating on. Then performing a decomposition on our k items takes O(k sqrt(k)) time, which don't look that much worse than O(k log k) (which would be O(n^2 log n ) in our original form).

Really its just about data amount, and doubling your amount of data is not the same as doubling n.