concepts/ 0040755 0000771 0000764 00000000000 10220220473 010646 5 ustar km fft concepts/index.html 0100644 0000771 0000764 00000003351 10220217607 012647 0 ustar km fft
Glas: Table of contents
Table of contents
- Concepts
-
- Mathematics concepts
- Linear algebra concepts
- Models
concepts/group_concept.html 0100644 0000771 0000764 00000004251 10220217476 014413 0 ustar km fft
Glas: Group concept
Group concept
Description
A group is an algebraic structure on a finite or infinite set
equipped with an operator (in the following we use the notation '@'
for the operator).
Let a and b be arbitrary elements of the group.
The following properties hold:
- closure: a @ b is an element of the group.
- associativity: ( a @ b ) @ c = a @ ( b @ c )
- identity: there is an element, denoted by e, so that a @ e = a
- inverse: for each a, there is an element u so that
a @ u = e.
Refinement of
Assignable,
DefaultConstructible
and
EqualityComparable.
Notation
X |
type that is a model of Group |
a, b |
Object of type X |
e |
identity element |
Definitions
Valid expressions
In addition to those defined by Assignable,
DefaultConstructible
and
EqualityComparable:
Name |
Expression |
Return type |
Expression semantics
Name |
Expression |
Precondition |
Semantics |
Postcondition |
Complexity guarantees
Invariants
Models
Notes
concepts/abelian_group_concept.html 0100644 0000771 0000764 00000002120 10220217272 016051 0 ustar km fft
Glas: AbelianGroup concept
AbelianGroup concept
Description
An abelian group is a commutative Group.
Let a and b be arbitrary elements of the group.
The following properties are assumed:
- commutativity: a @ b = b @ a for all a
and b in the group.
Refinement of
Group
Notation
Definitions
Valid expressions
Expression semantics
Complexity guarantees
Invariants
Commutativity |
a @ b = b @ a |
Models
- int
- float
- double
- std::complex<float>
- std::complex<double>
Notes
concepts/multiplicative_group_concept.html 0100644 0000771 0000764 00000005226 10220217760 017525 0 ustar km fft
Glas: MultiplicativeGroup concept
MultiplicativeGroup concept
Description
An AdditiveGroup (denoted as (G,*)) is a Group with the multiplication (*)
as operator.
For an MultiplicativeGroup
- the identity element is denoted as '1',
- the inverse element of a is denoted as '1/a'.
Refinement of
Group.
Notation
X |
type that is a model of Group |
a, b |
Object of type X |
1 |
identity element |
Definitions
Valid expressions
In addition to those defined by Group
Name |
Expression |
Return type |
Identity element |
one(a) |
void |
Multiplication |
a * b |
X |
Division |
a / b |
X |
Multiplication assignment |
a *= b |
X |
Division assignment |
a /= b |
X |
Expression semantics
Name |
Expression |
Precondition |
Semantics |
Postcondition |
One element |
one(a) |
|
Set a to the identity element (1) |
|
Multiplication |
a * b |
|
|
|
Division |
a / b |
|
equivalent to a * (1/b) |
|
Multiplication assignment |
a *= b |
|
equivalent to a = a * b |
|
Division assignment |
a /= b |
|
equivalent to a = a / b |
|
Complexity guarantees
Invariants
Inherited from Group.
Models
- double without 0.0
- std::complex<double> without 0.0
- non-zero rational numbers
Notes
concepts/additive_group_concept.html 0100644 0000771 0000764 00000005447 10220217360 016264 0 ustar km fft
Glas: AdditiveGroup concept
AdditiveGroup concept
Description
An AdditiveGroup (denoted as (G,+)) is a Group with the addition (+)
as operator.
For an AdditiveGroup
- the identity element is denoted as '0',
- the inverse element of a is denoted as '-a'.
Refinement of
Group.
Notation
X |
type that is a model of Group |
a, b |
Object of type X |
0 |
identity element |
Definitions
Valid expressions
In addition to those defined by Group
Name |
Expression |
Return type |
Identity element |
zero(a) |
void |
Addition |
a + b |
X |
Subtraction |
a - b |
X |
Addition assignment |
a += b |
X |
Subtraction assignment |
a -= b |
X |
Negation |
-a |
X |
Expression semantics
Name |
Expression |
Precondition |
Semantics |
Postcondition |
Zero element |
zero(a) |
|
Set a to the zero element (0) |
|
Addition |
a + b |
|
|
|
Subtraction |
a - b |
|
equivalent to a + (-b) |
|
Addition assignment |
a += b |
|
equivalent to a = a + b |
|
Subtraction assignment |
a -= b |
|
equivalent to a += -b |
|
Negation |
-a |
|
Equivalent to 0 - a |
|
Complexity guarantees
Invariants
Inherited from Group.
Models
- int
- float
- double
- std::complex<float>
- std::complex<double>
Notes
concepts/additive_abelian_group_concept.html 0100644 0000771 0000764 00000002607 10220216216 017731 0 ustar km fft
Glas: AdditiveAbelianGroup concept
AdditiveAbelianGroup concept
Description
An AddititiveAbelianGroup is an
AbelianGroup equipped with the
addition (+) operator.
Refinement of
AbelianGroup and
AdditiveGroup.
Notation
X |
type that is a model of Group |
a, b |
Object of type X |
0 |
Zero element: identity element for addition |
Definitions
Valid expressions
None in addition to those defined by AdditiveGroup.
Expression semantics
Name |
Expression |
Precondition |
Semantics |
Postcondition |
Complexity guarantees
Invariants
Models
- int
- float
- double
- std::complex<float>
- std::complex<double>
Notes
concepts/ring_concept.html 0100644 0000771 0000764 00000005427 10220220332 014205 0 ustar km fft
Glas: Ring concept
Ring concept
Description
A ring is an algebraic structure that is a
abelian group for the addition
with a multiplication operator '*' such that
- closure: a * b is an element of the ring
- associative: (a*b)*c = a*(b*c)
- pre-distributive: a * (b + c) = a * b + a * c
- post-distributive: (a + b) * c = a * c + b * c
- multiplicative identity such that a * 1 = 1 * a = a
Refinement of
AdditiveAbelianGroup
Notation
X |
type that is a model of Field |
a, b |
Object of type X |
0 |
Zero element: identity for addition |
1 |
One element: identity for multiplication |
Definitions
Valid expressions
In addition to those defined by AdditiveAbelianGroup:
Name |
Expression |
Return type |
One element |
one( a ) |
void |
Multiplication |
a * b |
X |
Multiplication assignment |
a *= b |
X |
Expression semantics
Name |
Expression |
Precondition |
Semantics |
Postcondition |
One element |
one( a ) |
|
Set a to the one element (1) |
|
Multiplication |
a * b |
|
|
|
Multiplication assignment |
a *= b |
|
equivalent to a = a * b |
|
Complexity guarantees
Invariants
Commutativity for Addition |
a + b = b + a |
Commutativity for Multiplication |
a * b = b * a |
Negation |
(-a) + a = 0 and a-a = 0 |
Models
- int
- float
- double
- std::complex<float>
- std::complex<double>
Notes
concepts/commutative_ring_concept.html 0100644 0000771 0000764 00000001240 10220216226 016616 0 ustar km fft
Glas: CommutativeRing concept
CommutativeRing concept
Description
A commutative ring is a Ring
in which the multiplication operation is commutative.
Refinement of
Ring
Notation
Definitions
Valid expressions
Expression semantics
Complexity guarantees
Invariants
Models
Notes
concepts/field_concept.html 0100644 0000771 0000764 00000003653 10220216232 014334 0 ustar km fft
Glas: Field concept
Field concept
Description
A field is a
CommutativeRing
where 0 is different from 1 and
each element a≠0 has the inverse 1/a.
Hence, a field is a
AdditiveAbelianGroup
and a MultiplicativeGroup
for the whole set without 0.
Refinement of
CommutativeRing
Notation
Definitions
Valid expressions
The expressions from CommutativeRing and:
Name |
Expression |
Return type |
Division |
a / b |
X |
Division assignment |
a /= b |
X |
Expression semantics
Name |
Expression |
Precondition |
Semantics |
Postcondition |
Division |
a / b |
b≠0 |
equivalent to a = a * (1/b) |
|
Division assignment |
a /= b |
b≠0 |
equivalent to a = a / b |
|
Complexity guarantees
Invariants
The invariants of
CommutativeRing and:
Inversion |
for a≠0 we have a / a = 1 |
Models
Notes
concepts/vector_space_concept.html 0100644 0000771 0000764 00000006036 10220220473 015726 0 ustar km fft
Glas: VectorSpace concept
VectorSpace concept
Description
A vector space is an algebraic structure over a
Field of values.
It is an
AdditiveAbeleanGroup for the addition and has
a scalar multiplication.
Refinement of
AdditiveAbeleanGroup.
Associated types
scalar_type: Field over which the vector space is defined |
Notation
X |
A type that is a model of VectorSpace |
v,w |
Object of type X |
a |
object of type convertible to X::scalar_type |
0 |
zero vector, i.e. the identity for the addition |
0 |
zero scalar, i.e. the identity for the addition in the Field X::scalar_type |
Definitions
Valid expressions
In addition to those defined by
AdditiveAbelianGroup:
Name |
Expression |
Type requirements |
Return type |
Scalar multiplication |
a * v |
|
X |
|
Scalar division |
v / a |
|
X |
|
Scalar multiplication |
v *= a |
|
X |
|
Scalar division |
v /= a |
|
X |
|
Expression semantics
Name |
Expression |
Precondition |
Semantics |
Postcondition |
Scalar multiplication |
a*v |
|
|
|
Scalar division |
v / a |
a!=0 |
equivalent to (1/a) * v |
|
Scalar multiplication |
v*=a |
|
v=a*v |
|
Scalar division |
v/=a |
a!=0 |
v=v/a |
|
Complexity guarantees
Invariants
In addition to those of
AdditiveAbelianGroup:
Models
Notes
concepts/vector_concept.html 0100644 0000771 0000764 00000011274 10220216245 014555 0 ustar km fft
Glas: Vector concept
Vector concept
Description
The Vector concept is intended to define a vector that can be used
in linear-algebra operations.
A vector contains n entries of type value_type, numbered
from 0 to n-1.
If the value_type satisfies the requirements of the
AdditiveAbelianGroup concept,
Vector is a
refinement of AdditiveAbelianGroup.
If the value_type satisfies the requirements of the
VectorSpace concept,
Vector is a
refinement of VectorSpace.
Note that if the value_type is a Field,
Vector is a VectorSpace over
value_type.
This is the most common situation in linear algebra.
Vector thus inherits the algebraic structure from its entries.
Refinement of
DefaultConstructible
[1].
The vector is also a refinement of
Assignable if the vector's value_type is a model of
Assignable.
The vector is also a refinement of AdditiveAbelianGroup
if the vector's value_type is a
AdditiveAbelianGroup.
The vector is also a refinement of VectorSpace
if the vector's value_type is a
VectorSpace.
Associated types
In addition to those defined by
DefaultConstructible,
Assignable,
AdditiveAbelianGroup,
and VectorSpace:
size_type |
Type of the matrix size (row index number, column index number) |
value_type |
Type of vector entries |
Notation
X |
Type that is a model of the Vector concept |
v |
object of type X |
a |
object of type X::value_type |
Definitions
Valid expressions
In addition to those defined by
DefaultConstructible,
and, if X::value_type is a model of Assignable,
those defined by Assignable,
and, if X::value_type is a model of AdditiveAbelianGroup,
those defined by AdditiveAbelianGroup:
and, if X::value_type is a model of VectorSpace,
those defined by VectorSpace:
Name |
Expression |
Type requirements |
Return type |
Size constructor[2] |
X(n) |
X::value_type is DefaultConstructible |
X |
Size |
size() |
|
size_type |
Expression semantics
Complexity guarantees
Invariants
Models
Notes
[1]Vector being
default-constructible does not require the vector entries to be initialized.
The reason for this is that this
initialisation generally takes linear time.
[2] The size-constructor is not
the same as the default fill constructor.
The difference is that the size-constructor is
not required to initialise all of its elements to
value_type().
The reason for this is that this
initialisation generally takes linear time.
concepts/matrix_concept.html 0100644 0000771 0000764 00000011620 10220216250 014546 0 ustar km fft
Glas: Matrix concept
Matrix concept
Description
The Matrix concept is intended to define a matrix that can be used
in linear-algebra operations.
A matrix contains m rows and n columns, numbered
from 0 to m-1 and
from 0 to n-1 respectively.
The entry in row i and column j has type value_type.
If the value_type satisfies the requirements of the
AdditiveAbelianGroup concept,
Matrix is a
refinement of AdditiveAbelianGroup.
If the value_type satisfies the requirements of the
Field concept,
Matrix is a
refinement of VectorSpace.
This is the most common situation in linear algebra.
[1]
Matrix thus inherits the algebraic structure from its entries.
Refinement of
DefaultConstructible
[2].
The matrix is also a refinement of
Assignable if the matrix X::value_type is a model of
Assignable.
The matrix is also a refinement of a AdditiveAbelianGroup
if the vector's value_type is a
AdditiveAbelianGroup.
The matrix is also a refinement of VectorSpace
if the matrix' value_type is a
Field.
Associated types
In addition to those defined by
DefaultConstructible,
Assignable,
AdditiveAbelianGroup,
and VectorSpace:
size_type |
Type of the matrix size (row index number, column index number) |
value_type |
Type of matrix entries |
Notation
X |
Type that is a model of the Matrix concept |
v |
object of type X |
a |
object of type X::value_type |
Definitions
Valid expressions
In addition to those defined by
DefaultConstructible
and, if X::value_type is a model of Assignable,
those defined by Assignable,
and, if X::value_type is a model of AdditiveAbelianGroup,
those defined by AdditiveAbelianGroup,
and, if X::value_type is a model of Field,
those defined by VectorSpace:
Expression semantics
Complexity guarantees
Invariants
Models
Notes
[1]We assume here that the value_type is
a field rather than a vector space. This is stricter than for the Vector
concept. It is easier to understand and this is the reason why we have
defined only the Vector concept with the more general situation.
The modification for the Matrix concept is straightforward.
[2]Matrix being
default-constructible does not require the matrix entries to be initialized.
The reason for this is that this
initialisation generally takes linear time.
[3] The size-constructor is not
the same as the default fill constructor.
The difference is that the size-constructor is
not required to initialise all of its elements to
value_type().
The reason for this is that this
initialisation generally takes linear time.
concepts/banach_space_concept.html 0100644 0000771 0000764 00000005050 10220216254 015635 0 ustar km fft
Glas: BanachSpace concept
BanachSpace concept
Description
A Banach space is a
VectorSpace.
A VectorSpace becomes a Banach space if it is equipped with a norm,
denoted by ||x||.
Refinement of
Associated types
In addition to those defined by VectorSpace:
real_type: the result of the norm function |
Notation
X |
A type that is a model of BanachSpace |
v |
Object of type X |
Definitions
Valid expressions
In addition to those defined by VectorSpace:
Name |
Expression |
Type requirements |
Return type |
Norm |
v.norm() |
|
real_type |
|
Expression semantics
Name |
Expression |
Precondition |
Semantics |
Postcondition |
Norm |
v.norm() |
|
|
v.norm() ≥ 0 |
Complexity guarantees
Invariants
- v.norm() ≥ 0
- v.norm() = 0 iff v=0
Models
Notes
concepts/hilbert_space_concept.html 0100644 0000771 0000764 00000003605 10220216257 016061 0 ustar km fft
Glas: HilbertSpace concept
HilbertSpace concept
Description
A Hilbert space is a
BanachSpace, equipped with
an inner product, denoted by <y,x> where
the norm is induced from the inner product as
||x|| = <x,x>1/2.
Refinement of
Associated types
Those defined by BanachSpace:
Notation
X |
A type that is a model of HilbertSpace |
v,w |
Object of type X |
Definitions
Valid expressions
In addition to those defined by BanachSpace:
Name |
Expression |
Type requirements |
Return type |
Inner product |
inner_prod( v, w ) |
|
value_type |
|
Expression semantics
Name |
Expression |
Precondition |
Semantics |
Postcondition |
Inner product |
inner_prod( v, w ) |
|
|
|
Complexity guarantees
Invariants
Models
Notes
concepts/euclidean_space_concept.html 0100644 0000771 0000764 00000002561 10220216263 016356 0 ustar km fft
Glas: EuclideanSpace concept
EuclideanSpace concept
Description
This is a Hilbert space equipped over the field of real or complex values
with the Euclidean inner product.
It is only defined for the
Vector concept, although one could imagine
similar concepts for the
Matrix concept.
For a vector, <x, y> is defined as
the sum of conj( yi ) * xi.
The induced norm is
||x||2 is the square root of the sum of
|xi|2
Refinement of
Associated types
Those defined by HilbertSpace:
Notation
Definitions
Valid expressions
Those defined by HilbertSpace:
Complexity guarantees
Invariants
Models
Notes
concepts/matrix.html 0100644 0000771 0000764 00000007457 10220217703 013054 0 ustar km fft
Glas: matrix< T >
matrix< T >
Description
Example
Definition
Template parameters
Parameter |
Description |
Default |
T |
Matrix value_type |
|
Model of
Matrix
Type requirements
Public base classes
Members
Free functions
Free function |
Where defined |
Comment |
void zero(matrix const&) |
Group |
T is a Group. |
matrix operator*(matrix::value_type, matrix const&) |
VectorSpace |
T is a Field. |
concepts/vector.html 0100644 0000771 0000764 00000010576 10220220410 013033 0 ustar km fft
Glas: vector< T >
vector< T >
Description
Example
- vector< double >
- vector< vector< double > >
Definition
Template parameters
Parameter |
Description |
Default |
T |
Vector value_type |
|
Model of
Vector
Type requirements
Public base classes
Members
Free functions
Free function |
Where defined |
Comment |
void zero(vector const&) |
Group |
T is a Group. |
template <class S> vector operator*(S, vector const&) |
VectorSpace |
T is a model of VectorSpace
where S = VectorSpace::scalar_type. |
concepts/norm_1_space.html 0100644 0000771 0000764 00000003521 10220220041 014067 0 ustar km fft
Glas: norm_1_space< V >
norm_1_space< V >
Description
The 1-norm is defined for the
Vector and
Matrix concepts.
The value_type must be a model of the
Field concept, so that we
have vector spaces.
For a Vector
the 1-norm is defined as
norm_1( m ) = Σi |vi|
For a Matrix
the 1-norm is defined as
norm_1( v ) = maxj Σi |vi,j|
Example
Definition
Template parameters
Parameter |
Description |
Default |
V |
VectorSpace type |
|
Model of
BanachSpace
Type requirements
V is a model of the
Vector
or Matrix concepts.
Public base classes
Members
All members of V with, in addition,
concepts/norm_2_space.html 0100644 0000771 0000764 00000003536 10220220105 014077 0 ustar km fft
Glas: norm_2_space< V >
norm_2_space< V >
Description
The 2-norm is defined for the
Vector and
Matrix concepts.
The value_type must be a model of the
Field concept, so that we
have vector spaces.
For a Vector
the 2-norm is defined as
norm_2( m ) = ( Σi |vi|2 )1/2
For a Matrix
the 2-norm is defined as
norm_2( v ) = largest singular value of v
Example
Definition
Template parameters
Parameter |
Description |
Default |
V |
VectorSpace type |
|
Model of
BanachSpace
Type requirements
V is a model of the
Vector
or Matrix concepts.
Public base classes
Members
All members of V with, in addition,
concepts/norm_frobenius_space.html 0100644 0000771 0000764 00000003134 10220220201 015721 0 ustar km fft
Glas: norm_frobenius_space< V >
norm_frobenius_space< V >
Description
The Frobenius-norm is defined for the
Matrix concept.
The value_type must be a model of the
Field concept, so that we
have a vector space.
The Frobenius-norm is defined as
norm_2( v ) = ( Σi,j |vi,j|2 )1/2
Example
Definition
Template parameters
Parameter |
Description |
Default |
V |
Matrix type |
|
Model of
BanachSpace
Type requirements
V is a model of the
Matrix concept.
Public base classes
Members
All members of V with, in addition,
concepts/norm_inf_space.html 0100644 0000771 0000764 00000003561 10220220145 014514 0 ustar km fft
Glas: norm_inf_space< V >
norm_inf_space< V >
Description
The infinity norm is defined for the
Vector and
Matrix concepts.
The value_type must be a model of the
Field concept, so that we
have vector spaces.
For a Vector
the infinity norm is defined as
norm_inf( m ) = maxi |vi|
For a Matrix
the infinity norm is defined as
norm_inf( v ) = maxi Σj |vi,j|
Example
Definition
Template parameters
Parameter |
Description |
Default |
V |
VectorSpace type |
|
Model of
BanachSpace
Type requirements
V is a model of the
Vector
or Matrix concepts.
Public base classes
Members
All members of V with, in addition,
concepts/euclidean_space.html 0100644 0000771 0000764 00000002775 10220216316 014651 0 ustar km fft
Glas: euclidean_space< V >
euclidean_space< V >
Description
Example
Definition
Template parameters
Parameter |
Description |
Default |
V |
Vector type |
|
Model of
EuclideanSpace
Type requirements
V is a model of the
Vector
concept with real or complex value_type.
Public base classes
Members
All members of V with, in addition,