Keywords

1 Introduction

Solving systems of linear equations is essential in modern engineering. Highly complex physical systems, which would require extremely complex formulae to describe, are approximated with high accuracy by a very large set of linear equations. In order to get reliable results, uncertainty, which is inevitable in real life problems, should be taken into account in any computations. Therefore, solving linear systems is one of the fundamental problems of interval computations, wherein “to solve a system” usually means to enclose a parametric solution set by an interval vector as tightly as possible.

The assumption that the coefficients of a linear system vary independently within given ranges is rarely satisfied in practice. That is why recently a big effort was made to develop methods that are able to solve the so-called parametric interval linear systems, i.e., linear systems with elements being functions of parameters that are allowed to vary within given intervals. Until now, several such methods have been developed, one can mention approximate methods described in [4, 5, 11, 17, 18].

The tightest is the resulting interval vector, the better. The narrowest possible interval enclosure is called the interval hull solution (or simply the hull). When the parametric solution is monotone with respect to all the parameters, the hull can be computed by solving at most 2n real systems. The monotonicity approach was investigated, e.g., in [6, 12, 15, 20]. Generally, checking monotonicity is a very complex task and for large scale problems the monotonicity based methods are inefficient. Therefore, in this paper an attempt is made to reduce the computational time of the monotonicity approach. Vectorisation and parallelisation techniques are used for this purpose. It is worth to add that the monotonicity approach is extensively used in the interval global optimisation. Thus, the improvement of the efficiency of the monotonicity approach will significantly influence the efficiency of the interval global optimisation and monotonicity based methods.

The paper is organised as follows. The Sect. 2 contains preliminaries on solving parametric interval linear systems with two disjoint sets of parameters. In the Sect. 3, the monotonicity approach for computing interval hull solution is outlined. Section 4 presents general concepts of vectorisation and parallelisation. This is followed by a description of the monotonicity approach. Next, some illustrative examples of truss structures and the results of computational experiments are presented. The paper ends with concluding remarks.

2 Preliminaries

Italic font will be used for real quantities, while bold italic font will denote their interval counterparts. Let \(\mathbbm {I}\mathfrak {R}\) denote a set of real compact intervals \({{\varvec{x}}}=\left[ \underline{x},\,\overline{x}\right] = \left\{ x\in \mathbbm {R}\;|\;\underline{x}\leqslant x\leqslant \overline{x}\right\} \). For two intervals \(a,\,b\in \mathbbm {I}\mathfrak {R}\), \(a\geqslant b\), \(a\leqslant b\) and \(a=b\) will mean that, resp., \(\underline{a}\geqslant \overline{b}\), \(\overline{a}\geqslant \underline{b}\), and \(\underline{a}=\underline{b}\) \(\wedge \) \(\overline{a}=\overline{b}\). \(\mathbbm {I}\mathfrak {R}^n\) will denote interval vectors and \(\mathbbm {I}\mathfrak {R}^{n\times n}\) will denote square interval matrices [10]. The midpoint \(\check{x}=(\underline{x}+\overline{x})/2\) and the radius \(\text{ r }({{\varvec{x}}})=(\overline{x}-\underline{x})/2\) are applied to interval vectors and matrices componentwise.

Definition 1

A parametric linear system

$$\begin{aligned} A(p)x=b(p) \end{aligned}$$
(1)

is a linear system with elements that are real valued functions of a K-dimensional vector of parameters \(p=(p_1,\ldots ,p_K)\in \mathfrak {R}^K\), i.e., for each \(i,j=1,\ldots ,n\),

$$\begin{aligned} \begin{array}{l} A_{ij}:\mathfrak {R}^K\ni (p_1,\ldots ,p_K)\rightarrow A_{ij}(p_1,\ldots ,p_K)\in \mathfrak {R},\\ b_i:\mathfrak {R}^K\ni (p_1,\ldots ,p_K)\rightarrow b_i(p_1,\ldots ,p_K)\in \mathfrak {R}. \end{array} \end{aligned}$$
(2)

Functions describing the elements of a parametric linear system can be generally divided into affine-linear and nonlinear. However, nonlinear dependencies can be easily reduced to affine-linear using affine arithmetic [1]. Therefore, the following consideration are limited to the affine-linear case.

Remark: Obviously, the transformation from nonlinear to affine-linear dependencies causes some loss of information [1], nevertheless, the approach based on affine arithmetic is worth considering as it is simple and quite efficient.

Definition 2

A parametric interval linear system with affine dependencies is given by

$$\begin{aligned} A(p)x=b(p), \end{aligned}$$
(3)

where \(A(p)=A^{(0)}+\textstyle \sum _{k=1}^KA^{(k)}p_k\), \(b(p)=b^{(0)}+\textstyle \sum _{k=1}^Kb^{(k)}p_k\), \(A^{(i)}\in \mathfrak {R}^{n\times n}\), and \(b^{(i)}\in \mathfrak {R}^n\) (\(i=1,\ldots ,K\)).

If the involved parameters are subject to uncertainty, which means that they allowed to vary within given intervals (the interval-based model of uncertainty is adopted in this paper), then a parametric interval linear system is obtained.

Definition 3

A parametric interval linear system is an infinite set (family) of parametric real linear systems

$$\begin{aligned} \left\{ A(p)x=b(p)\;|\;p\in {{\varvec{p}}}\right\} . \end{aligned}$$
(4)

The family (4) is usually written in a compact form as

$$\begin{aligned} A({{\varvec{p}}})x({{\varvec{p}}})=b({{\varvec{p}}}). \end{aligned}$$
(5)

Definition 4

A parametric (united) solution set of the system (5) is a set of solutions to all systems from the family (4), i.e.,

$$\begin{aligned} S({{\varvec{p}}})=\left\{ \,x\,|\,\exists p\in {{\varvec{p}}},\;\;A(p)x=b(p)\right\} . \end{aligned}$$
(6)

In order that the solution set be bounded, the parametric matrix \(A({{\varvec{p}}})\) must be regular, i.e., A(p) must be non-singular for each \(p\in {{\varvec{p}}}\).

In general case, the problem of computing the solution set (6) as well as its hull are NP-hard. Therefore, usually an outer interval enclosure, i.e., the vector \({{\varvec{x}}}^{\mathrm {out}}\supset S({{\varvec{p}}})\), is computed instead. However, when the solution of a parametric system is monotone with respect to all parameters, then the hull of the solution set can be computed with polynomial cost in n and K. If the solution is monotone with respect to some of the parameters, then a good quality outer solution can be computed with polynomial cost in n and K.

3 Monotonicity Approach

For the sake of completeness of the paper, a brief reminder of the monotonicity approach is presented below.

Let \(E^K=\left\{ e\in \mathbbm {R}^K\;|\;e_k\in \{-1,\,0,\,1\},\,k=1,\,\ldots ,\,K\right\} \). For \({{\varvec{p}}}\in \mathbbm {I}\mathfrak {R}^K\), \(e\in E^K\), \(p^e_k=\underline{p}_k\) if \(e_k=-1\), \(p^e_k=\check{p}_k\) if \(e_k=0\), and \(p^e_k=\overline{p}_k\) if \(e_k=1\).

Theorem 1

Let \(A({{\varvec{p}}})\) be regular and let the functions \(x_i(p)=\left\{ A^{-1}(p)\cdot b(p)\right\} _i\) be monotone on an interval box \(\mathbf p \in \mathbbm {I}\mathfrak {R}^K\), with respect to each parameter \(p_k\) (\(k=1,\,\ldots ,\,K\)). Then, for each \(i=1,\ldots ,n\),

$$\begin{aligned} \left\{ \Box S({{\varvec{p}}})\right\} _i=\left[ \left\{ A\left( p^{-e^i}\right) ^{-1}b\left( p^{-e^i}\right) \right\} _i, \, \left\{ A\left( p^{e^i}\right) ^{-1}b\left( p^{e^i}\right) \right\} _i \right] , \end{aligned}$$
(7)

where \(e^i_k=\text{ sign }\frac{\partial x_i}{\partial p_k}\), \(k=1,\ldots ,K\).

Now consider the family of parametric linear equations (4) and assume that \(A_{ij}(p)\) and \(b_i(p)\) (\(i,\,j=1,\,\ldots ,\,n\)) are continuously differentiable in \({{\varvec{p}}}\). If x is a solution to the system \(A(p)x=b(p)\), then \(x=A(p)^{-1}b(p)\), which means that x is a function of p. Thus, the global monotonicity properties of the solution with respect to each parameter \(p_k\) can be verified by checking the sign of derivatives \(\frac{\partial x}{\partial p_k}(p)\) on the domain \({{\varvec{p}}}\). The differentiation of the Eq. (1) with respect to \(p_k\) (\(k=1,\,\ldots ,\,K\)) yields

$$\begin{aligned} \left\{ \left. A(p)\frac{\partial x}{\partial p_k}(p)=\frac{\partial b}{\partial p_k}(p) -\frac{\partial A(p)}{\partial p_k}x(p)\;\right| \;p\in {{\varvec{p}}}\right\} . \end{aligned}$$
(8)

Since \(A_{ij}(p)\), \(b_j(p)\) are affine linear functions of p, thus \(\frac{\partial A_{ij}}{\partial p_k}\), \(\frac{\partial b_i}{\partial p_k}\) are constant on \({{\varvec{p}}}\). Hence, the approximation of \(\frac{\partial x}{\partial p_k}(p)\) can be obtained by solving the following K parametric linear systems

$$\begin{aligned} A({{\varvec{p}}})\frac{\partial x}{\partial p_k}=b'({{\varvec{x}}}^*) \end{aligned}$$
(9)

where \(b'({{\varvec{x}}}^*)=\{b^{(k)}-A^{(k)}x^*\;|\;x^*\in {{\varvec{x}}}^*\}\) and \({{\varvec{x}}}^*\) is some initial solution to the system (5).

For a fixed i (\(1\leqslant i\leqslant n\)), let \({{\varvec{D}}}_{ki}\) denotes the interval estimate of \(\{\frac{\partial x_i}{\partial p_k}(p)\;|\;p\in {{\varvec{p}}}\}\) obtained by solving the Eq. (9). Now assume that each \({{\varvec{D}}}_{ki}\) (\(k=1,\,\ldots ,\,K\)) has a constant sign or equals 0. Then, in order to calculate the hull of \(\{S({{\varvec{p}}})\}_i\), the elements of the vector \(e^i\) must be determined as follows: \(e^i_k=1\) if \({{\varvec{D}}}_{ki}\geqslant 0\), \(e^i_k=0\) if \({{\varvec{D}}}_{ki}\equiv 0\), and \(e^i_k=-1\) if \({{\varvec{D}}}_{ki}\leqslant 0\). If the sign of some of the partial derivatives was not determined definitely, then a new vector of parameters is constructed by substituting the respective endpoints for interval parameters. The process of determining the sign of derivatives restarts and continues until no further improvement is obtained. The algorithm of the method is presented below. Parts of code in Algorithm 1 which are candidates for parallelisation and vectorisation are indicated by comments.

figure a

4 Parallelisation and Vectorisation

Parallelisation is the process of converting sequential code into a multi-threaded one in order to use available processors simultaneously. The parallelisation process often also includes vectorisation, because contemporary central processor units are able to perform operations on multiple data in a single instruction. This ability is called SIMD (single instruction multiple data). It allows to convert an algorithm from a scalar implementation, in which a single instruction can deal with one pair of operands at a time, to a vector process, where a single instruction can refer to a vector of operands (series of adjacent values). Vectorisation can be carried out either automatically by contemporary C++ compilers or forced by a programmer usually by using an appropriate pragma. Vectorisation not always brings performance improvement due to additional data movement and pipeline synchronisation. Thus, the vectorisation can be profitable for loops that run for a suitable number of iterations. Such loops however, must meet certain constraints including continuous access of memory, no data dependency and only single exit from the loop.

The newest Intel and AMD processors implements Advanced Vector Extensions (AVX) instruction set that operates on 256 bit SIMD registers. For double precision floating point numbers this allows to perform basic mathematical operations on 4 numbers at once. Example of addition with SIMD is shown in Fig. 1. In the experiments presented in this paper, the newest Intel C++ compiler (16.0) is used. This compiler efficiently analyse the code and indicates which loops are worth to be vectorised. It can also be forced to vectorise other loops by using #pragma simd. Both these mechanisms are used in the experiments to improve the efficiency of the monotonicity approach.

Fig. 1.
figure 1

Loops vectorisation

Full size image

While vectorisation plays only a supporting role in parallelisation process, the main benefit can be achieved by transforming the code so that it is able to utilise many threads simultaneously. This is realised in either task parallelism model (the so called fork-join parallelism) or single program multiple data (SPMD) model. For a single multi-core processor the first model is usually implemented as parallel constructs nest in a straightforward manner [21].

Similarly to the vectorisation, parallelisation can be done automatically by a C++ compiler or can be guided by a user. When using an Intel compiler three methods can be used: Threading Building Blocks (TBB) or Cilk Plus (originally developed in MIT) and auto parallelisation with OpenMP. The two first methods use work-stealing strategy, in which each processor maintains its own local queue and when the local queue is empty, the worker randomly steals work from victim worker queues, while in OpenMP a master thread forks a specified number of slave threads and divides a task among them. In our experiments all three types of parallelisation are used.

5 Numerical Examples

To check the performance of the monotonicity approach some illustrative examples of structural mechanical systems are considered. The obtained results are compared with the results given by a method (it should be added that there are several such methods [2, 4, 12, 17], however a great majority of them yields very similar results, especially for the problem considered here) for computing outer interval solution of parametric interval linear systems.

Fig. 2.
figure 2

Example 1: 5-bay 4-floor plane truss structure

Full size image

Example 1

(5-bay 4-floor plane truss structure). For the plane truss structure shown in Fig. 2 the displacements of the nodes are computed. The truss is subjected to downward forces \(P_2=P_3=P_4=20\)[kN] as depicted in the figure; Young’s modulus \(Y=2.0\times 10^{11}\)[Pa], cross-section area \(C=0.0001\)[m\(^2\)], length of horizontal bars is \(L=10\)[m], and the lenght of vertical bars is \(H=5\)[m]. The truss is fully supported at the nodes 1 and 5. This gives 72 interval parameters. Table 1 shows the relative times for various combinations of vectorisation and parallelisation. The baseline has been set to the variant of the program that used no vectorisation and no parallelisation. Tests have been run on the machine with Intel Xeon 1220v2 CPU with 4 cores and no hyper-threading ability.

Table 1. Comparison of the computation times for Example 1
Full size table

The times presented in the table show the benefits that can be achieved by the vectorisation of the monotonicity algorithm, which are 10 % on average. Automatic parallelisation does not improve the processing times and in one case it consumes even more time. This is due to the fact, that compiler cannot be sure that the processing data are fully independent. When Cilk and TBB methods have been used, the improvement is significant and when combined with vectorisation they can improve the processing times up to four times.

Example 2

(Baltimore bridge built in 1870). Consider the plane truss structure shown in Fig. 3 subjected to downward forces of \(\text{ P }_1=80[kN]\) at node 11, \(\text{ P }_2=120[kN]\) at node 12 and \(\text{ P }_1\) at node 15; Young’s modulus \(\text{ Y }=2.1\times 10^{11}\ [Pa]\), cross-section area \(\text{ C }=0.004\)[m\(^2\)], and length \(L=1\)[m]. Assume that the stiffness of 23 bars is uncertain by \(\pm 5\,\%\). This gives 23 interval parameters.

Fig. 3.
figure 3

Example 2: Baltimore bridge

Full size image
Table 2. Comparison of the computation times for Example 2
Full size table

The comparison of the performance of different variants of code vectorisation and paralellisation is presented in Table 2. Again the tests have been run on Intel Xeon 1220v3 processor with 4 cores. For the more complex problem the benefit in processing times is higher and equals up to 15 %. When we combine either Cilk or TBB parallelisation method with vectorisation the overall improvement reaches more than four times. The difference between both two fork-joint models is unconvincing, so each of them can be successfully applied. The overall computational experiments prove, that the more complex problem is the more is the benefit from using parallelisation and vectorisation.

6 Conclusions

Checking the sign of the derivatives is a clue to test the global monotonicity of the solution of parametric linear systems. The global monotonicity enables calculating the interval hull solution easily by solving at most 2n real systems. The main deficiency of the monotonicity approach is its poor performance. As shown by the performed experiments, the performance of the monotonicity approach can be improved by using techniques such as vectorisation and parallelisation, which are available for contemporary C++ and Fortran compilers like Visual C++, Gnu cpp or Intel compiler in Parallel Studio XE.

The presented methodology can be applied to any problem which requires solving linear systems with input data dependent on uncertain parameters. The monotonicity approach is also a crucial acceleration techniques for interval global optimisation applied for the problem of solving parametric interval linear systems. The improved version of monotonicity approach can significantly decrease the computational time of the interval global optimisation.