Boost logo

Glas :

Re: [glas] dotc and dotu in glas

From: Andrew Lumsdaine (lums_at_[hidden])
Date: 2006-05-02 08:18:41


I may be looking at this from a slightly different point of view (and
this difference in viewpoints has come up in other discussions on
this list). I am coming at this from the point of view of "concepts"
rather than particular types or implementations.

If the glas are truly going to be Generic in the sense of Stepanov
and Musser, the most important part of the library is the concept
definitions -- i.e., what are the formally defined sets of
requirements that types must meet in order to be used with generic
algorithms. The point of a generic algorithm is to be usable with as
wide a variety of types as possible. Thus, as Stepanov suggests, one
needs to start with the algorithms. Specific vector or matrix types
are simply specific instances of concepts in this view. But, to be
immediately usable, such instances should provide functionality (and
syntax) that matches the concept definitions.

I would therefore suggest analyzing a few Hilbert-space (and related)
algorithms to determine what the right Hilbert-space concepts are.
Two prototypical algorithms that would be very useful in this regard
would be CG and BiCG.

The interface to CG would be expected to look something like this
(leaving out preconditioning and other details for the moment):

template < typename LinearOperator, typename HilbertSpace>
int cg(const LinearOperator& A, HilbertSpace& x, const HilbertSpace& b);

Within cg() there will be calls to dot() and dot() in this case
should be considered a valid expression for the HilbertSpace
concept. Mathematically, this dot() needs to be a conjugate dot for
a proper Hilbert space. Similarly, it needs to be a conjugate dot
for the cg() algorithm to work properly (as cg() requires a Hilbert
space).

Now consider BiCG.

template < typename LinearOperator, typename HilbertSpace>
int bicg(const LinearOperator& A, HilbertSpace& x, const
HilbertSpace& b);

In this case, bicg also calls dot() -- however this dot() is not a
conjugate dot() in the case of a complex Hilbert space. In this case
it is probably incorrect for this function to be called dot() at all
-- it is simply a bilinear form.

The concept taxonomy of linear algebra must correspond to the
mathematical underpinnings. The HilbertSpace concept needs to match
the mathematical notion of a Hilbert space, for which the dot()
operation is well-defined (and is conjugate for the complex case).

I think some of the current discussion about glas vector types is
focusing on implementation (instances) rather than concepts. A
straightforward approach to defining such instances would be one-to-
one with concepts so that the types immediately model the concepts.
However, the toolbox approach that was suggested would also allow the
types to model the concepts (using particular compositions of
toolboxes).

On May 2, 2006, at 7:17 AM, Karl Meerbergen wrote:

> I am a bit puzzled with your answer. What exactly would you want to
> support in the glas core? dot(), dotu(), dotc(), all three?
>
> I would like to recall the idea of toolboxes. The glas core provides
> basic functions defined following a clear definition in the
> documentation. In that respect, I agree with Toon's proposal to
> provide
> the function dot=dotu defined as dot(x,y) = sum_i x[i] * y[i]. If dot
> were defined as sum_i conj(x[i]) * y[i], you have to use dot( conj(x),
> y) to get dotu(x,y), i.e. apply conj twice of undo the conj internally
> in the implementation. So, this is a practical reason, nothing to do
> with maths.
>
> On toolbox level, functions and concepts can be defined with less
> "ambiguity" and stronger mathematical support. E.g. in linear algebra
> (LA) we use x^H y to denote the (complex conjugate) dot product and
> x^T
> y for the unconjugate dot product. So, we can provide something like
> herm(x)*y and trans(x)*y, or perhaps x^HERM * y and x^TRANS * y, which
> is very close to LA notation. In an earlier discussion there was
> agreement on this notation.
>
> We could also consider a vectorspace toolbox where vectorspace
> concepts
> can be defined with inner products, norms etc. Why? Because it is not
> clear to define "the" inner product on LA level, or "the" norm. On
> that
> level, a matrix vector product can be interpreted as a map from one
> space to another, or some linear operator in the same space.
>
> The advantage of using toolboxes is that vectors and matrices can
> get a
> narrow interpretation, where specific notation applies. From previous
> discussions it has been clear that we hardly agree on notation and
> concepts. Toolboxes can partly solve this, since they add
> interpretation.
>
>
> Karl
>
>
>
> Sanz, Christophe wrote:
>
>> Quoting Karl Meerbergen <Karl.Meerbergen_at_[hidden]>:
>>
>>
>>
>>> Removing ambiguity is a strong argument for having two different
>>> functions, dotc() and dotu().
>>>
>>> Karl
>>>
>>>
>>>
>> Do you mean that there is no interest for a GLAS to define a proper
>> specialisation of the dot function for a collection of values with
>> complex
>> types, which specialisation could co-exist with both dotu & dotc?
>>
>>
>>
>>> Sanz, Christophe wrote:
>>>
>>>
>>>
>>>> Quoting Karl Meerbergen <Karl.Meerbergen_at_[hidden]>:
>>>>
>>>>
>>>>
>>>>
>>>>
>>>>> As far as I understand, Toon was talking about core syntax, not
>>>>> functionality:
>>>>> is there a problem with dot(conj(x),y) for the euclidean inner
>>>>> product?
>>>>>
>>>>> Karl
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>> Possibly not but there seem to remain some ambiguity pertaining
>>>> to the
>>>>
>>>>
>>> choice of
>>>
>>>
>>>> the proper specialisation of the dot function for collection of
>>>> complex
>>>>
>>>>
>>> types.
>>>
>>>
>>>> The maths would suggest that it is dotc while (eg:) the MTL
>>>> would suggest
>>>>
>>>>
>>> that
>>>
>>>
>>>> it is dotu. Possibly the latter option was just too
>>>> straightforward to be
>>>> avoided in first place but retaining option 1 could be well worth a
>>>> confirmation. Was that Matthias meant?
>>>>
>>>>
>>>>
>>>>
>>>>> Matthias Troyer wrote:
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>> I want to strongly support Andrew's statement. If one wants
>>>>>> only one
>>>>>> dot product then the proper inner product for a complex
>>>>>> Hilbert space
>>>>>> needs to be chosen.
>>>>>>
>>>>>> Matthias
>>>>>>
>>>>>> On May 1, 2006, at 10:59 AM, Andrew Lumsdaine wrote:
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>> Both are needed.
>>>>>>>
>>>>>>> In the Iterative Template Library, both are required in order
>>>>>>> for the
>>>>>>> solvers to work properly with complex vectors.
>>>>>>>
>>>>>>> Mathematically, dotc() is a proper inner product for a
>>>>>>> complex Hilbert
>>>>>>> space, dotu() is not. If a single dot() function is going to
>>>>>>> be used
>>>>>>> for inner product, mathematically it must be equivalent to
>>>>>>> dotc().
>>>>>>>
>>>>>>> Use cases are very important when creating interfaces for a
>>>>>>> generic
>>>>>>> library. I would suggest taking a look at ITL and IETL to
>>>>>>> see how
>>>>>>> generic linear concepts at this level of abstraction are used.
>>>>>>>
>>>>>>> Toon Knapen wrote:
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>> I was wondering if we need an equivalent for both the dotc and
>>>>>>>> dotu of
>>>>>>>> BLAS in glas? I suggest to only have _one_ dot function
>>>>>>>> (which is
>>>>>>>> equivalent to the dot in blas for vectors of reals and which
>>>>>>>> corresponds
>>>>>>>> to dotu for vectors of complex values). To perform the
>>>>>>>> equivalent of
>>>>>>>> dotc one could then write dot(conj(x),y). This is IMHO
>>>>>>>> clearer and
>>>>>>>> the
>>>>>>>> expression-template mechanism will avoid that this compound
>>>>>>>> expression
>>>>>>>> will induce a performance penalty.
>>>>>>>>
>>>>>>>> I just added an equivalent to dotc but I plan to add the
>>>>>>>> solution as
>>>>>>>> described above, benchmark both and than remove the dotc
>>>>>>>> equivalent
>>>>>>>> afterwards (supposing the benchmark will not show any
>>>>>>>> performance
>>>>>>>> differences of both approaches).
>>>>>>>>
>>>>>>>> toon
>>>>>>>>
>>>>>>>>
>>>>>>>> _______________________________________________
>>>>>>>> glas mailing list
>>>>>>>> glas_at_[hidden]
>>>>>>>> http://lists.boost.org/mailman/listinfo.cgi/glas
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>> _______________________________________________
>>>>>>> glas mailing list
>>>>>>> glas_at_[hidden]
>>>>>>> http://lists.boost.org/mailman/listinfo.cgi/glas
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>> _______________________________________________
>>>>>> glas mailing list
>>>>>> glas_at_[hidden]
>>>>>> http://lists.boost.org/mailman/listinfo.cgi/glas
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>> --
>>>>> ==============================================
>>>>> Karl Meerbergen
>>>>>
>>>>> Free Field Technologies
>>>>>
>>>>> NEW ADDRESS FROM FEBRUARY 1st ONWARD:
>>>>>
>>>>> Axis Park Louvain-la-Neuve
>>>>> rue Emile Francqui, 1
>>>>> B-1435 Mont-Saint Guibert - BELGIUM
>>>>>
>>>>> Company Phone: +32 10 45 12 26
>>>>> Company Fax: +32 10 45 46 26
>>>>> Mobile Phone: +32 474 26 66 59
>>>>> Home Phone: +32 2 306 38 10
>>>>> mailto:Karl.Meerbergen_at_[hidden]
>>>>> http://www.fft.be
>>>>> ============================================
>>>>>
>>>>>
>>>>>
>>>>> _______________________________________________
>>>>> glas mailing list
>>>>> glas_at_[hidden]
>>>>> http://lists.boost.org/mailman/listinfo.cgi/glas
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>> _______________________________________________
>>>> glas mailing list
>>>> glas_at_[hidden]
>>>> http://lists.boost.org/mailman/listinfo.cgi/glas
>>>>
>>>>
>>>>
>>>>
>>>>
>>> --
>>> ==============================================
>>> Karl Meerbergen
>>>
>>> Free Field Technologies
>>>
>>> NEW ADDRESS FROM FEBRUARY 1st ONWARD:
>>>
>>> Axis Park Louvain-la-Neuve
>>> rue Emile Francqui, 1
>>> B-1435 Mont-Saint Guibert - BELGIUM
>>>
>>> Company Phone: +32 10 45 12 26
>>> Company Fax: +32 10 45 46 26
>>> Mobile Phone: +32 474 26 66 59
>>> Home Phone: +32 2 306 38 10
>>> mailto:Karl.Meerbergen_at_[hidden]
>>> http://www.fft.be
>>> ============================================
>>>
>>>
>>>
>>> _______________________________________________
>>> glas mailing list
>>> glas_at_[hidden]
>>> http://lists.boost.org/mailman/listinfo.cgi/glas
>>>
>>>
>>>
>> _______________________________________________
>> glas mailing list
>> glas_at_[hidden]
>> http://lists.boost.org/mailman/listinfo.cgi/glas
>>
>>
>>
>
>
> --
> ==============================================
> Karl Meerbergen
>
> Free Field Technologies
>
> NEW ADDRESS FROM FEBRUARY 1st ONWARD:
>
> Axis Park Louvain-la-Neuve
> rue Emile Francqui, 1
> B-1435 Mont-Saint Guibert - BELGIUM
>
> Company Phone: +32 10 45 12 26
> Company Fax: +32 10 45 46 26
> Mobile Phone: +32 474 26 66 59
> Home Phone: +32 2 306 38 10
> mailto:Karl.Meerbergen_at_[hidden]
> http://www.fft.be
> ============================================
>
>
>
> _______________________________________________
> glas mailing list
> glas_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/glas