Welcome to spl’s documentation!¶
PSYDAC is a Python/Fortran 2003 library for B-Splines/NURBS and Computer Aided Design Algorithms.
PSYDAC can be used in three different ways:
- Fortran 90/95 subroutines through the file fortran/src/bsplines/bspline.F90
- Fortran 2003 objects, mainly the mapping and cad objects
- The same objects as in 2. but through Python
First Steps with PSYDAC¶
This document is meant to give a tutorial-like overview of PSYDAC.
The green arrows designate “more info” links leading to advanced sections about the described task.
By reading this tutorial, you’ll be able to:
- compile a simple PSYDAC file
- get familiar with parallel programing paradigms
- create, modify and build a PSYDAC project.
Install PSYDAC¶
B-Splines and NURBS¶
We start this section by recalling some basic properies about B-splines curves and surfaces. We also recall some fundamental algorithms (knot insertion and degree elevation).
For a basic introduction to the subject, we refer to the books [LP95] and [Far02].
A B-Splines family, of order
, can be generated using a non-decreasing sequence of knots
.
B-Splines series¶
The j-th B-Spline of order is defined by the recurrence relation:
where,
for and
.
We note some important properties of a B-splines basis:
- B-splines are piecewise polynomial of degree
,
- Compact support; the support of
is contained in
,
- If
, then only the B-splines
are non vanishing at
,
- Positivity:
,
- Partition of unity
,
- Local linear independence,
- If a knot
has a multiplicity
then the B-spline is
at
.
Knots vector families¶
There are two kind of knots vectors, called clamped and unclamped. Both families contains uniform and non-uniform sequences.
The following are examples of such knots vectors
- Clamped knots (open knots vector)
- uniform


- non-uniform


- Unclamped knots
- uniform


- non-uniform


B-Spline curve¶
The B-spline curve in associated to knots vector
and the control polygon
is defined by :
In (Fig. ref{figBSplineCurve}), we give an example of a quadratic B-Spline curve, and its corresponding knot vector and control points.


We have the following properties for a B-spline curve:
- If
, then
is just a B’ezier-curve,
is a piecewise polynomial curve,
- The curve interpolates its extremas if the associated multiplicity of the first and the last knot are maximum (i.e. equal to
), i.e. open knot vector,
- Invariance with respect to affine transformations,
- Strong convex-hull property:
if , then
is inside the convex-hull associated to the control points
,
- Local modification : moving the
control point
affects
, only in the interval
,
- The control polygon approaches the behavior of the curve.
Note
In order to model a singular curve, we can use multiple control points : .
Multivariate tensor product splines¶
Let us consider knot vectors
. For simplicity, we consider that these knot vectors are open, which means that
knots on each side are duplicated so that the spline is interpolating on the boundary, and of bounds
and
. In the sequel we will use the notation
.
Each knot vector
, will generate a basis for a Schoenberg space,
. The tensor product of all these spaces is also a Schoenberg space, namely
, where
. The cube
, will be referred to as a patch.
The basis for is defined by a tensor product :
where, .
A typical cell from is a cube of the form :
.
Deriving a B-spline curve¶
The derivative of a B-spline curve is obtained as:
where , and
are generated using the knot vector
, which is obtained from
by reducing by one the multiplicity of the first and the last knot (in the case of open knot vector), i.e. by removing the first and the last knot.
More generally, by introducing the B-splines family generated by the knots vector
obtained from
by removing the first and the last knot
times, we have the following result:
proposition¶
The derivative of the curve
is given by
where, for
By denoting and
the first and second derivative of the B-spline curve
, it is easy to show that:
We have,
,
,
,
.
Example¶
Let us consider the quadratic B-spline curve associated to the knots vector and the control points
:
we have,
where
The B-splines are associated to the knot vector
.
Fundamental geometric operations
By inserting new knots into the knot vector, we add new control points without changing the shape of the B-Spline curve. This can be done using the DeBoor algorithm [dB01]. We can also elevate the degree of the B-Spline family and keep unchanged the curve [HHM05]. In (Fig. ref{refinement_curve_B_Spline}), we apply these algorithms on a quadratic B-Spline curve and we show the position of the new control points.
Knot insertion¶
After modification, we denote by the new parameters.
are the new control points.
One can insert a new knot , where
. For this purpose we use the DeBoor algorithm [dB01]:
Many other algorithms exist, like blossoming for fast insertion algorithm. For more details about this topic, we refer to [NT93].
Order elevation¶
We can elevate the order of the basis, without changing the curve. Several algorithms exist for this purpose. We used the one by Huang et al. [PP91], [HHM05].
A quadratic B-spline curve and its control points. The knot vector is .

The curve after a h-refinement by inserting the knots while the degree is kept equal to
.

The curve after a p-refinement, the degree was raised by (using cubic B-splines).

The curve after duplicating the multiplicity of the internal knots ,
this leads to a B’ezier description. We can then, split the curve into
pieces (sub-domains), each one will corresponds to a quadratic B’ezier curve.

Translation¶
Rotation¶
Todo
not yet available
Scaling¶
Todo
not yet available
References
[dB01] | (1, 2) C. de Boor. A Practical Guide to Splines. Applied Mathematical Sciences. Springer New York, 2001. ISBN 9780387953663. URL: https://books.google.de/books?id=m0QDJvBI_ecC. |
[Far02] | G. Farin. Curves and surfaces for CAGD: a practical guide. Morgan Kaufmann Pub. Inc., San Francisco, CA, USA, 2002. ISBN 1-55860-737-4. |
[HHM05] | (1, 2) Qi-Xing Huang, Shi-Min Hu, and Ralph R. Martin. Fast degree elevation and knot insertion for b-spline curves. Computer Aided Geometric Design, 22(2):183 – 197, 2005. URL: http://www.sciencedirect.com/science/article/B6TYN-4DXBTHR-2/2/d5b3eec2f4c230c8051623c1c000beae, doi:DOI: 10.1016/j.cagd.2004.11.001. |
[LP95] | W. Tiller L. Piegl. The NURBS Book. Springer-Verlag, Berlin, Heidelberg, 1995. second ed. |
[NT93] | Goldman R. N. and Lyche T. Knot Insertion and Deletion Algorithms for B-Spline Curves and Surfaces. SIAM, Philadelphia, USA, 1993. ISBN 9780898713060. |
[PP91] | Hartmut Prautzsch and Bruce Piper. A fast algorithm to raise the degree of spline curves. Comput. Aided Geom. Des., 8:253–265, October 1991. URL: http://portal.acm.org/citation.cfm?id=124930.124932, doi:10.1016/0167-8396(91)90015-4. |
GLT¶
Where do the GLTs come from?¶
The main aim of this paragraph is to present a crucial example that highlights the importance of the GLT algebra when dealing with linear systems coming from the discretization of PDEs. Let us start with some preliminaries. In detail, we will recall the notion of symbol of a matrix-sequence and the basic idea behind the GLT theory.
Spectral preliminaries¶
The following one is a rather informal definition of symbol of a matrix-sequence.
example:
When ,
,
,
means
References
Exterior Algebra¶
Let be a real vector space of dimension
.
Definition, Alternating algebraic forms:
For each , we define
as the space of alternating
-linear maps
.
Note
,
is the dual space of
(the space of covectors)
Definition, Exterior product:
For and
, their exterior (wedge) product is given by:
for all . Where the sum is over all permutations
of
,
for which
and
.
Note
- The exterior product is bilinear, associative,
- anti-commutative:
for all
and
.
Definition, Grassmann Algebra:
Grassmann Algebra is defined by:
This is a anti-commutative graded algebra. Also called Exterior Algebra of
In the case of , we have:
,
,
, using Riesz representation theorem,
, using the map
.
Basis¶
Let be a basis of
and
the associated dual basis for
(
).
For any increasing permutations , we have:
thus the algebraic
-forms
,
form a basis for
and
.
Definition, Interior product:
Let be a
-form, and
. The interior product of
and
is the
-form
defined by:
- We have for
,
and
:
Definition, Inner product:
If is has an inner product, then
is endowed with an inner product given by:
where the sum is over increasing sequences , and
is any orthonormal basis.
Orientation and Volume form¶
Todo
add Orientation and Volume form
Definition, Pullback:
A linear transformation of vector spaces induces a transformation
, called the pullback, and given by:
The pullback acts contravariantly: if
then,
Let V be a subspace of W. For the inclusion , we can define its pullback
:
this is a surjection of
onto
.
If W has an inner product and is the orthogonal projection. We can define its pullback
:
this an injection of
onto
.
Let us consider the composition : shortstack{
\
}
shortstack{
\
}
, and its pullback
.
Definition, The tangential and normal parts:
associates for each
its tangential part
with respect to
:
associates for each
its normal part
with respect to
.
The tangential part of vanishes if and only if the image of
in
vanishes.
Let be an oriented inner product space, with volume form
. Let
.
We can define a new linear map
as the composition of
such as:
and the canonical isomorphism of onto
, and using the Riesz representation theorem,
there exists an element
such that :
, i.e.:
Definition, The Hodge star operation:
The linear map which maps onto
is called the Hodge star operator.
- If
is any positively oriented orthonormal basis, and
a permutation, we have
, thus the Hodge star is an isometry.
and
- the image of
in
vanishes if and only if
vanishes.
Exterior Calculus on manifolds and Differential forms¶
Let be a smooth manifold, of dimension
.
we denote by
the tangent space. This is a vector space of dimension
,
- tangent bundle
,
- Applying the exterior algebra to the tangent spaces, we obtain the exterior forms bundle, whose elements are pairs
with
and
.
- a differential
-form
is a section of this bundle. This is a map which associates to each
an element
,
- if the map
is smooth (whenever
are smooth), we say that
is a smooth differential
-form,
- we define
the space of all smooth
-forms on
,
,
- if the map
is
, we define differential
-forms with less smoothness
.
Let be a smooth manifold, of dimension
.
Exterior product:
if and
, we may define
as
and the Grassmann algebra
Differential forms can be differentiated and integrated, without recourse to any additional structure, such as a metric or a measure.
Exterior differentiation:
For each, can define the
-form
, such as:
where the hat is used to indicated a suppressed argument.
This defines a graded linear operator of degree , of
onto
.
We have the following properties:
,
- (Pullback) let
be a smooth map of
onto
. Then
and
,
- (Interior product) the interior product of a differential
-form
with a vector field
,
- we obtain a
-form by :
,
- (Trace operator) the pullback
of
is the trace operator
Integration:
- If
is an oriented, piecewise smooth
-dimensional submanifold of
, and
is a continuous
-form, then th integral
is well defined :
- [0-forms] can be evaluated at points,
- [1-forms] can be integrated over directed curves,
- [2-forms] can be integrated over directed surfaces,
- (Inner product) The
-inner product of two differential
-forms on an oriented Riemannian manifold
is defined as :
The completion of in the corresponding norm defines the Hilbert space
.
We have the following results:
- (Integration) if
is an orientation-preserving diffeomorphism, then
Theorem, Stokes theorem:
If is an oriented
-manifold with boundary
, then
Theorem, Integration by parts:
If is an oriented
-manifold with boundary
, then
Sobolev spaces of differential forms¶
As for the classical case, we can define the Sobolev spaces as:
is the space of differential
-forms such that
.
. The associated norm is :
coincides with
,
coincides with
,
- for
, we have
, strictly.
Cohomology and De Rham Complex¶
The De Rham complex is the sequence of spaces and mappings
Since, , we have
If is an oriented Riemannian manifold, we have the following cohomology:
The coderivative operator is defined as:
- we have
is a graded linear operator of degree
.
is the formal adjoint of
whenever
or
vanishes near the boundary.
- we define the spaces
we have
.
- we obtain the dual complex
Cohomology with boundary conditions¶
Let be the subspace of
of smooth
-forms with compact support. We have
.
The De Rham complex with the compact support is
Recall that the closure of in
is
The version of the last complex is
Definition, Harmonic forms:
The harmonic -forms are the differential
-forms that verify the differential equations
this defines the following space,
We can also define the following space,
As we can see, .
Proposition, Poincaré duality:
There is an isomorphism between the th De Rham cohomology space and the
th cohomology space with boundary conditions.
Homological Algebra and Hilbert complexes¶
Homological Algebra¶
- A cochain complex is a sequence of vector spaces and linear maps
-cocycles
,
-coboundaries
,
-cohomology
,
- we say that the sequence is exact, if the cohomology vanishes (i.e.
),
- Given two cochain complexes
, a cochain map
(such as
)
maps
-cochains to
-cochains and
-coboundaries to
-coboundaries, thus induces a map
.
Let be two cochain complexes,
The inclusion
is a cochain map and thus induces a map of cohomology
,
If there exists a cochain projection of
onto
, (this leads to
) so
.
Thus, is injective and
is surjective. Hence, if one of the cohomology spaces
vanishes,
then so does
Cycles and boundaries of the De Rham complex¶
-cocycles
-coboundaries
- each of the spaces of cycles is closed in
(
), as well in
.
- each of the spaces of boundaries is closed in
.
- let
denotes the orthogonal complement in
,
DeRham sequences¶
here without boundary conditions
Pullbacks¶
In the case where the physical domain is the image of a logical domain
by a smooth mapping
(at least
), we have the following parallel diagrams
Where the mappings and
are called pullbacks and are given by
where is the jacobian matrix of the mapping
.
Note
The pullbacks and
are isomorphisms between the corresponding spaces.
Discrete Spaces¶
Let us suppose that we have a sequence of finite subspaces for each of the spaces involved in the DeRham sequence. The discrete DeRham sequence stands for the following commutative diagram between continuous and discrete spaces
When using a Finite Elements methods, we often deal with a reference element, and thus we need also to apply the pullbacks on the discrete spaces. In fact, we have again the following parallel diagram
Since, the pullbacks are isomorphisms in the previous diagram, we can define a one-to-one correspondance
We have then, the following results
Discrete DeRham sequence for B-Splines¶
Buffa et al [BSV09] show the construction of a discrete DeRham sequence using B-Splines, (here without boundary conditions)
1d case¶
- DeRham sequence is reduced to
- The recursion formula for derivative writes
- we have
which is a change of basis as a diagonal matrix
- Now if
, with and expansion
, we have
- If we introduce the B-Splines coefficients vector
(and
for the derivative), we have
where is the incidence matrix (of entries
and
)
Discrete derivatives:
2d case¶
In 2d, the are two De-Rham complexes:
and
Let be the identity matrix, we have
Discrete derivatives:
3d case¶
Discrete derivatives:
Note
From now on, we will denote the discrete derivative by for the one going from
to
.
Algebraic identities¶
Let us consider the discretization of the exterior derivative
multiplying by a test function and integrating over the whole computation domain, we get
let ,
and
be the vector representation of
,
and
. We get
where
On the other hand, using the coderivative, we get
Let us now introduce the following matrix
hence,
Therefor, we have the following important result
Proposition:
References
[BSV09] | A. Buffa, G. Sangalli, and R. Vazquez. Isogeometric analysis in electromagnetics: b-splines approximation. Comput. Methods Appl. Mech. Engrg, 199:1143–1152, 2009. |
API¶
You will find here both the Fortran doxygen documentation as well as the Python-API.