Systems of Linear Equations

Stephen Andrilli , David Hecker , in Elementary Linear Algebra (Fifth Edition), 2016

Exercises for Section 2.1

1.

Use Gaussian Elimination to solve each of the following systems of linear equations. In each case, indicate whether the system is consistent or inconsistent. Give the complete solution set, and if the solution set is infinite, specify three particular solutions.

⋆(a)

− 5 x 1 − 2 x 2 + 2 x 3 = 16 3 x 1 + x 2 − x 3 = − 9 2 x 1 + 2 x 2 − x 3 = − 4

(b)

3 x 1 − 3 x 2 − 2 x 3 = 23 − 6 x 1 + 4 x 2 + 3 x 3 = − 40 − 2 x 1 + x 2 + x 3 = − 12

⋆(c)

3 x 1 − 2 x 2 + 4 x 3 = − 54 − x 1 + x 2 − 2 x 3 = 20 5 x 1 − 4 x 2 + 8 x 3 = − 83

(d)

− 2 x 1 + 3 x 2 − 4 x 3 + x 4 = − 17 8 x 1 − 5 x 2 + 2 x 3 − 4 x 4 = 47 − 5 x 1 + 9 x 2 − 13 x 3 + 3 x 4 = − 44 − 4 x 1 + 3 x 2 − 2 x 3 + 2 x 4 = − 25

⋆(e)

6 x 1 − 12 x 2 − 5 x 3 + 16 x 4 − 2 x 5 = − 53 − 3 x 1 + 6 x 2 + 3 x 3 − 9 x 4 + x 5 = 29 − 4 x 1 + 8 x 2 + 3 x 3 − 10 x 4 + x 5 = 33

(f)

5 x 1 − 5 x 2 − 15 x 3 − 3 x 4 = − 34 − 2 x 1 + 2 x 2 + 6 x 3 + x 4 = 12

⋆(g)

4 x 1 − 2 x 2 − 7 x 3 = 5 − 6 x 1 + 5 x 2 + 10 x 3 = − 11 − 2 x 1 + 3 x 2 + 4 x 3 = − 3 − 3 x 1 + 2 x 2 + 5 x 3 = − 5

(h)

5 x 1 − x 2 − 9 x 3 − 2 x 4 = 26 4 x 1 − x 2 − 7 x 3 − 2 x 4 = 21 − 2 x 1 + 4 x 3 + x 4 = − 12 − 3 x 1 + 2 x 2 + 4 x 3 + 2 x 4 = − 11

2.

Suppose that each of the following is the final augmented matrix obtained after Gaussian Elimination. In each case, give the complete solution set for the corresponding system of linear equations.

⋆(a)

1 − 5 2 3 − 2 0 1 − 1 − 3 − 7 0 0 0 1 2 0 0 0 0 0 − 4 − 2 5 0

(b)

1 − 3 6 0 − 2 4 0 0 1 − 2 8 − 1 0 0 0 0 0 1 0 0 0 0 0 0 − 3 5 − 2 0

⋆(c)

1 4 − 8 − 1 2 − 3 0 1 − 7 2 − 9 − 1 0 0 0 0 1 − 4 0 0 0 0 0 0 − 4 − 3 2 0

(d)

1 − 7 − 3 − 2 − 1 0 0 1 2 3 0 0 0 1 − 1 0 0 0 0 0 − 5 1 4 − 2

⋆3.

Solve the following problem by using a linear system: A certain number of nickels, dimes, and quarters totals $17. There are twice as many dimes as quarters, and the total number of nickels and quarters is twenty more than the number of dimes. Find the correct number of each type of coin.

⋆4.

Find the quadratic equation y  = ax 2  + bx  + c that goes through the points (3,20),(2,11), and (−2,15).

5.

Find the cubic equation y  = ax 3  + bx 2  + cx  + d that goes through the points (1,2),(2,−12),(−2,56), and (3,−54).

⋆6.

The general equation of a circle is x 2  + y 2  + ax  + by  = c. Find the equation of the circle that goes through the points (6,8),(8,4), and (3,9).

7.

Let A  = 2 3 4 0 1 1 − 2 1 5 3 0 1 , B = 2 1 − 5 2 3 0 4 1 1 . Compute R(AB) and (R(A))B to verify that they are equal, if

⋆(a)

[(a)]R: 3 ← − 3 2 + 3 .

(b)

R: 2 ⇔ 4 .

8.

This exercise asks for proofs for parts of Theorem 2.1.

►(a)

Prove part (1) of Theorem 2.1 by showing that R(AB)   =   (R(A))B for each type of row operation ((I), (II), (III)) in turn. (Hint: Use the fact from Section 1.5 that the kth row of (AB)   =   (kth row of A)B.)

(b)

Use part (a) and induction to prove part (2) of Theorem 2.1.

9.

Explain why the scalar used in a Type (I) row operation must be nonzero.

10.

Suppose that A is an m × n matrix, B is in R m , and X 1 and X 2 are two different solutions to the linear system AX  = B.

(a)

Prove that if c is a scalar, then X 1  + c(X 2 −X 1) is also a solution to AX  = B.

(b)

Prove that if X 1  + c(X 2 −X 1)   =X 1  + d(X 2 −X 1), then c  = d.

(c)

Explain how parts (a) and (b) show that if a linear system has two different solutions, then it has an infinite number of solutions.

⋆11.

True or False:

(a)

The augmented matrix for a linear system contains all the essential information from the system.

(b)

It is possible for a linear system of equations to have exactly three solutions.

(c)

A consistent system must have exactly one solution.

(d)

Type (II) row operations are typically used to convert nonzero pivot entries to 1.

(e)

A Type (III) row operation is used to replace a zero pivot entry with a nonzero entry below it.

(f)

Multiplying matrices and then performing a row operation on the product has the same effect as performing the row operation on the first matrix and then calculating the product.

(g)

After Gaussian Elimination, if an augmented matrix has a row of all zeroes, then the corresponding linear system is inconsistent.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780128008539000025

Numerical Methods

L. Zheng , X. Zhang , in Modeling and Analysis of Modern Fluid Problems, 2017

8.1.1 Numerical Methods for Linear System of Equations

Linear systems of equations are associated with many problems in engineering and science, as well as with applications of mathematics to the social sciences and the quantitative study of business and economic problems. Consider to solve the linear system AX  = B:

A = [ a 11 a 12 … a 1 n a 21 a 22 … a 2 n a 31 … a 32 ... … … a 3 n … a n 1 a n 2 … a n n ] , X = [ x 1 x 2 x 3 ⋮ x n ] , B = [ b 1 b 2 b 3 ⋮ b n ]

where A is an n  × n matrix, X and B are both n  ×   1 column vector, respectively. The determinant of A denoted by detA or | A | , which provides existence and uniqueness results for linear systems when | A | ≠ 0 .

There are many numerical methods for solving linear systems of equations, such as Gaussian elimination, pivoting strategies, matrix inversion, matrix factorization, iterative techniques, etc. As an example, we present matrix factorization used in this book to illustrate applications, and one can find other methods in any textbook of numerical analysis.

Gaussian elimination is the principal tool in the direct solution of linear systems of equations. From study on the Gaussian elimination element method for Ax  = b, we know that the essence of the eliminating process is to perform n 2 ( n − 1 ) times sequential of the elementary row transformation on coefficient matrix A to transform the matrix into an upper triangular matrix. If Gaussian elimination can be performed on the linear system AX  = B without row interchanges, then the matrix A can be factored into the product of a lower-triangular matrix L and an upper-triangular matrix U. The factorization is particularly useful when it has the form A  = LU, where L is lower triangular and U is upper triangular, defined as follows:

L = [ 1 l 21 1 l 31 l 32 1 … … … l n 1 l n 2 … … l n n − 1 1 ] and U = [ u 11 u 12 u 13 … u 1 n u 22 u 23 … u 2 n u 33 … u 3 n … … u n n ] ,

then

(8.1) a i j = ∑ k = 1 n l i k u k j = { ∑ k = 1 i − 1 l i k u k j + u i j j ≥ i ∑ k = 1 j − 1 l i k u k j + l i j u j j j < i i , j = 1,2 , … , n

For i  =   1, a 1j   = u 1j , j  =   1, 2, …, n; and for j  =   1, a i1  = l i1 u 11, i  =   2, 3, …, n

We obtain

(8.2) u 1 j = a 1 j , j = 1,2 , … , n ,

(8.3) l i 1 = a i 1 / u 11 , i = 2,3 , … , n ,

(8.4) u i j = a i j − ∑ k = 1 i − 1 l i k u k j , i ≤ j ,

(8.5) l i j = ( a i j − ∑ k = 1 j − 1 l i k u k j ) / u j j , i > j ,

The factorization of the matrix can be divided into two kinds: the present lower triangular matrix is the unit of the triangular matrix, known as the Doolittle decomposition; and when the unit is on the upper triangular matrix it is called Crout decomposition.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780128117538000086

LINEAR ALGEBRA

C. Farhat , D. Rixen , in Encyclopedia of Vibration, 2001

Solving linear systems of equations is at the heart of most computational analysis methods. In order to compute a solution accurately and fast, the method for solving those systems must be chosen according to:

•

the properties of the matrix operator (i.e., symmetry, definite positiveness, singularity and sparsity)

•

the size of the system (from a few unknowns up to several millions)

•

the numerical conditioning of the system of equations

•

its capability to efficiently handle multiple right-hand sides

•

the burden of its implementation

•

its ability to run on vector or parallel computers.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B0122270851000035

Determinants

Alexander S. Poznyak , in Advanced Mathematical Tools for Automatic Control Engineers: Deterministic Techniques, Volume 1, 2008

Lemma 1.4. (Kronecker–Capelli)

A system of linear equations given in the form (1.17) has

•

a unique solution if m = n and

det undefined A = undefined [ a 11 a 12 ⋅ a 1 n a 21 a 22 ⋅ a 2 n ⋅ ⋅ ⋅ a n 1 a n 2 ⋅ a n n ] ≠ 0

•

infinitely many solutions if the minimal number of linearly independent rows of A (denoted by rank A) is equal to one of the extended matrices (denoted by rank [A | b]), that is,

rank A = rank [ a 11 a 12 ⋅ a 1 n a 21 a 22 ⋅ a 2 n ⋅ ⋅ ⋅ a n 1 a n 2 ⋅ a n n ] undefined = rank [ A | b ] = rank [ a 11 a 12 ⋅ a 1 n b 1 a 21 a 22 ⋅ a 2 n b 2 ⋅ ⋅ ⋅ ⋅ a n 1 a n 2 ⋅ a n n b n ]

•

no solutions (to be inconsistent) if

rank A ≠ rank [ A | b ]

The proof of this fact will be clarified in the next chapter where the inverse matrix will be introduced.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780080446745500043

Matrix Algebra

H. Yanai , H. Ishii , in International Encyclopedia of Education (Third Edition), 2010

Least-Squares g-Inverse

Given a system of linear equations Ax = b and b ∉ S( A ), then the system is not consistent, that is, this solution does not exist. In such a case, we need a least-squares solution such that ‖Ax − b ‖2 is minimized. The solution is written as x = A l − b where A l − Satisfies

AA l − A = A and ( AA l − ) ′ = AA l −

A l − can be written as (A′A)− A′ and is called a least-squares g-inverse of A. It should be noted that AA l − is the orthogonal projector onto S(A) and thus is unique for any choice of A l − . If A has column full rank, then (A′A)−1 A′ is one choice of A l − .

For example, if

A = [ 1 1 1 1 ]

then

A l − = [ a b 1 / 2 − a 1 / 2 − b ]

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780080448947013415

Systems of Linear Equations

Stephen Andrilli , David Hecker , in Elementary Linear Algebra (Fourth Edition), 2010

Highlights

■

A system of linear equations has either no solutions (inconsistent), one solution, or an infinite number of solutions (dependent).

■

The three row operations allowable in Gaussian elimination are: type (I): multiplying a row by a nonzero scalar, type (II): adding a multiple of one row to another, and type (III): switching two rows.

■

Performing any of the three row operations on the augmented matrix for a linear system does not alter the solution set of the system.

■

When performing Gaussian elimination on an augmented matrix, we proceed through the columns from left to right. When proceeding to the next column, the goal is to choose a nonzero pivot element in the next row that does not yet contain a pivot.

■

If the next logical pivot choice is nonzero, we convert that pivot to 1 (using a type (I) row operation), and zero out all entries below the pivot (using a type (II) row operation).

■

If the next logical pivot choice is a zero entry, and if a nonzero value exists in some row below this entry, a type (III) row operation is used to switch one such row with the current row.

■

If the next logical pivot choice is a zero entry, and all entries below this value are zero, then the current column is skipped over.

■

At the conclusion of the Gaussian elimination process, if the system is consistent, each nonpivot column represents an (independent) variable that can have any value, and the values of all other (dependent) variables are determined from the independent variables, using back substitution.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780123747518000184

Finite element methods

Brent J. Lewis , ... Andrew A. Prudil , in Advanced Mathematics for Engineering Students, 2022

Galerkin method

The choice of the weighting and shape functions produces different numerical methods: least squares, collocation (i.e., the sum of fixed points), and the Galerkin method, among other techniques. For finite element methods the most common is the Galerkin method, which sets the weighting function equal to the shape functions W ( x → ) = N i ( x → ) and searches for an approximate solution with error equal to zero. For each node this approach leads to equations of the form

(7.35) ∫ V ( ∇ N i ( x → ) ⋅ ∇ N → ( x → ) u → + N i ( x → ) f ( x → ) ) d V = 0 ,

which collectively produce a system of equations for the unknown components of u → . The components of u → are the unknown nodal values u ˜ i , which are not spatially varying and can therefore be factored from the integrals, leading to

(7.36) [ u 1 ∫ ∇ N 1 ∇ N 1 d V + u 2 ∫ ∇ N 1 ∇ N 2 d V + … + u n ∫ ∇ N 1 ∇ N n d V u 1 ∫ ∇ N 2 ∇ N 1 d V + u 2 ∫ ∇ N 2 ∇ N 2 d V + … + u n ∫ ∇ N 2 ∇ N n d V ⋮ u 1 ∫ ∇ N n ∇ N 1 d V + u 2 ∫ ∇ N n ∇ N 2 d V + … + u n ∫ ∇ N n ∇ N n d V ] = − [ ∫ N 1 f d V ∫ N 2 f d V ⋮ ∫ N n f d V ] .

Finally, factoring u → yields a matrix equation

(7.37) [ ∫ ∇ N 1 ∇ N 1 d V ∫ ∇ N 1 ∇ N 2 d V … ∫ ∇ N 1 ∇ N n d V ∫ ∇ N 2 ∇ N 1 d V ∫ ∇ N 2 ∇ N 2 d V … ∫ ∇ N 2 ∇ N n d V ⋮ ∫ ∇ N n ∇ N 1 d V ∫ ∇ N n ∇ N 2 d V … ∫ ∇ N n ∇ N n d V ] [ u 1 u 2 ⋮ u n ] = − [ ∫ N 1 f d V ∫ N 2 f d V ⋮ ∫ N n f d V ] ,

or in matrix form

(7.38) [ K ] u → = F → .

Here the matrix K is termed the "stiffness" matrix. The elements of the stiffness matrix have the form

(7.39) K i , j = ∫ ∇ N i ∇ N j d V .

Typically most of the entries in this matrix evaluate to zero because the shape functions are only nonzero in the elements which include the node (i.e., nonoverlapping shape functions yield zero for this integral). This produces a "sparse" matrix where most entries are zero and only the nonzero values are stored, which reduces the computational costs compared to "dense" matrices.

The calculation of the nonzero elements of the matrix K and the vector F → requires evaluation of the integrals on each finite element. In most finite element implementations, this calculation is usually performed numerically with a "quadrature" method that approximates an integral as a weighted sum of the integrand evaluated at specific points:

(7.40) ∫ g ( x → ) d V = ∑ i = 1 n w i g x → i .

Here w i are the quadrature weights applied to the integrand g x → evaluated at x → i and n is the number of points evaluated. The most widely used quadrature method is "Gaussian quadrature," which is exact for polynomials 2 n − 1 or less (see, for example, Section 9.5.3). Other quadrature techniques such as "Gauss–Kronrod" are sometimes utilized when estimates of the integration error are required. In practice it is often sufficient to integrate to a higher degree but skip the error test.

The element formulations are normally precalculated for standard equations and element types. The stiffness matrix is assembled by adding the contributions from each element in the mesh. This "stiffness" matrix depends on the partial differential equation, the boundary conditions, and the mesh.

Boundary conditions need to be applied that will constrain the system to obtain a nonsingular solution. If the system is nonlinear, an iterative approach is utilized in which the stiffness of each element is calculated using the previous solution. The stiffness is updated on each iteration along with the solution vector and the calculation proceeds until convergence is achieved. For example, a nonlinear system may involve the calculation of temperature, where the thermal conductivity itself is dependent on the temperature.

Once the linear system of equations from Eq. (7.38) is assembled, standard solution techniques can be applied as discussed in Chapter 4. There are two main approaches used for finite elements:

•

Direct matrix factorization. Techniques such as lower-upper factorization are more stable/robust and simpler to use and configure. However, it is slower for large problems and requires more memory.

•

Iterative methods. These methods solve the system by updating an initial guess; the most common are Krylov methods such as GMRES and BiCSTAB. They often require less memory and are faster than the direct factorization method for large (usually three-dimensional) problems. However, it is less stable for poorly/ill-conditioned problems.

Additional considerations for finite element method analysis

It is important to recognize that the finite element mesh does not have a physical meaning since the true solution does not depend on the mesh itself, and an infinite number of meshes can provide equivalent results. Changing the mesh a small amount should not substantially change the answer. If it does, the result is an artifact of the solution process and is not representative of the true solution. It is good practice to perform a mesh convergence study to ensure that refining the mesh does not strongly alter the solution. The mesh is simply a part of the finite element method, which must be small enough in order to "accurately" represent the solution.

On the other hand, the boundary conditions are extremely important and are physically relevant to the problem. They can be simple (e.g., a fixed displacement or constant temperature) or extremely complicated (e.g., with the contact of adjoining surfaces, friction between surfaces, or no slip flow).

One must also ensure that the element order is sufficient to capture the desired properties of the solution. For example, consider a displacement field which satisfies a solid mechanics model. Components of the strain (ϵ) and stress (σ) are related to the derivative of the displacement u such that

(7.41) ϵ x = ∂ u ∂ x ,

(7.42) σ x = E ϵ x = E ∂ u ∂ x ,

where E is the Young's modulus. For a linear triangular element, u ˜ ( x , y ) = a 0 + a 1 x + a 2 y = N 1 ( x , y ) u 1 + N 2 ( x , y ) u 2 + N 3 ( x , y ) u 3 from Eq. (7.15b) and Eq. (7.17), and therefore the strain is

(7.43) ∂ u ˜ ( x , y ) ∂ x = a 1 = u 1 ∂ N 1 ( x , y ) ∂ x + u 2 ∂ N 2 ( x , y ) ∂ x + u 3 ∂ N 3 ( x , y ) ∂ x

(7.44) = ( y 2 − y 3 ) u 1 + ( − y 1 + y 3 ) u 2 + ( y 1 − y 2 ) u 3 2 A ,

which is no longer a function of the spatial coordinates. Therefore, the strain and stress field within linear triangular shape functions cannot vary smoothly between elements. By contrast, the derivatives of higher-order triangular elements, or linear quadrilateral elements, are not constant and therefore better able to resolve the strain fields. In general there is no clear "best" element for all applications, i.e., this choice depends on the application. One needs to consider what features are expected/needed to be captured. Can rectangular elements be used? How significant are the gradients? Is there a region of interest? How many spatial derivatives are required?

Similarly, to achieve convergence one requires an acceptable error tolerance that depends on the quantity being solved for, the required accuracy needed for the solution, and the accuracy of the underlying physics and known material properties. Other considerations include (i) the available computing resources (i.e., the random-access memory [RAM] or central processing unit [CPU]); (ii) the degree of nonlinearity, which has a strong effect on the solution convergence (i.e., large deformation and geometric stiffness); (iii) the type of problem being solved (e.g., stationary, time-dependent, eigenvalue, frequency response); and (iv) whether the problem involves single physics or multiphysics (with one- or two-directional coupling). A more detailed introduction to finite elements is provided in Hutton (2004) and Zienkiewicz et al. (2013).

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780128236819000150

Linear Equations

William Ford , in Numerical Linear Algebra with Applications, 2015

Abstract

The solution of linear systems of equations is of paramount importance in engineering and science. This chapter introduces the basics of solving linear equations using Gaussian elimination. The method is introduced systematically by covering every step in the row reduction of the augmented matrix so that the portion corresponding to the coefficient matrix is in upper triangular form. The system may have no solution or infinitely many solutions. The chapter details the use of back substitution to find the solution to the upper triangular system, if it exists. Gaussian elimination can be used to compute the inverse matrix, although the inverse is rarely computed in practice; rather, it is used for theoretical purposes. The chapter proves the important result that a homogeneous system has a unique solution if and only if its coefficient matrix is invertible. The chapter concludes with the presentation of two practical applications, the solution to a truss and an electrical circuit problem.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780123944351000028

An Automatable Generic Strategy for Dynamic Load Balancing in Parallel Structured Mesh CFD Code

J.N. Rodrigues , ... M. Cross , in Parallel Computational Fluid Dynamics 1999, 2000

6 RESULTS

When solving a linear system of equations using a 200×300 Jacobi Iterative Solver on a heterogeneous system of processors, each processor has the same workload but their speeds (or number of users) differ. In this instance, the load imbalance is associated with the variation between processors, which shall be referred to as 'processor imbalance'. This means that when a fast processor gains cells from a slow processor, then these shall be processed at the processor's own weight, since the weight of the cells are not transferred. Figure 4a shows the timings for a cluster of nine workstations used to solve the above problem, where the load was forcibly balanced after every 1000th iteration (this was used to test the load balancing algorithm rather than when to rebalance the load). It can be seen that the maximum iteration time has been dramatically reduced, and the timings appear more 'balanced' after each rebalance, improving the performance of the code. Figure 4b shows that the load on the middle processor (the slowest) is being reduced each time, indicating that the algorithm is behaving as expected.

Figure 4a. The processor times used to solve 3000 iterations of the Jacobi Iterative Solver on a 3×3 workstation cluster, in which the load is redistributed after every 1000th iteration.

Figure 4b. The workloads on the 9 processors mentioned in Figure 4a after having balanced the load after every 1000th iteration, in which the middle processor is the slowest (IPX) and the others are a mixture of Ultras and S20's.

When running on a homogeneous system of processors, the timings should be adjusted differently before balancing subsequent dimensions, as the load imbalance is no longer associated with the variation between the processors since their speeds are the same.

The Southampton-East Anglia Model (SEA Code) [6] uses an oceanography model to simulate the fluid flow across the globe. Its computational load is naturally imbalanced. Typically, parallelising this type of code means that a discretised model of the Earth is partitioned onto a number of processors, each of which may own a number of land cells and a number of sea cells, as shown in Figure 5. Parallel inefficiency arises in the oceanography code, for example, when trying to model the flow of the ocean in the fluid flow solver, where few calculations are performed on processors owning a high proportion of land cells. This means that some processors will remain idle whilst waiting for other processors to complete their calculations, exhibiting natural imbalance, as the amount of computation depends on the varying depth of sea.

Figure 5. Example showing the Earth partitioned onto 9 processors, each represented by different colourings, where each processor owns a varying depth of sea upon which to compute on.

When running this code on the CRAY T3E in which the imbalance is solely due to the physical characteristics, the weight of the cell being moved should be transferred across onto the new owner. This type of problem shall be referred to as having 'physical imbalance', where the processor speeds are homogenous, and the computational load associated with each cell remains the same after the cell has been transferred onto a neighbouring processor.

Therefore it may be necessary to treat the different types of problem differently when load balancing, as the weight is related to the cell itself rather than the processor speed (as with processor imbalance).

Figure 6 shows the processor timings for a single iteration using the different balancing techniques, from which the following points can be ascertained. The processor timings appear unbalanced when no load balancing is undertaken, which suggests that there is a fair amount of idle time present. It is also noticeable that there is very little work being done by the processor who owns Europe and Russia (processor 9 in this case, in which a 4×3 topology is being used). The maximum processor time can be reduced simply by balancing the workload on each processor using the given methods; however, the processor timings are only 'balanced' when staggering the limits assuming physical imbalance (where processor 9 is then given a sufficient amount of work).

Figure 6. Shows the processor timings at iteration 16 for various types of load balancing on a 4×3 processor topology (note that Processor 9 contained Europe and Russia).

A more general overview can be seen in Figure 7, in which statistical measurements are given for each of the different balancing techniques. The aim is to reduce the maximum iteration time down towards the average time, as giving more work to the fast/light processor shall increase the minimum time. It is apparent that this is achieved only when balancing the problem assuming the correct problem type. A similar trend can be seen for various processor topologies in Figure 8, in which it is clear to say that any form of balancing is better than none, and that staggering the limits is better than changing them globally. These results suggest that the type of problem being balanced is an important factor and needs to be considered when performing any form of DLB.

Figure 7. Statistical measurements for the processor timings for iteration 16, for various types of load balancing on a 4×3 processor topology.

Figure 8. The execution times (CPU + Rebalancing time) using different types of load balancing for various processor topologies, for 2000 iterations.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780444828514500438

Linear Equations and Eigensystems

G.R. Lindfield , J.E.T. Penny , in Numerical Methods (Third Edition), 2012

2.1 Introduction

We start with a discussion of linear equation systems and defer discussion of eigensystems until Section 2.15. To illustrate how linear equation systems arise in the modeling of certain physical problems we will consider how current flows are calculated in a simple electrical network. The necessary equations can be developed using one of several techniques; here we use the loop-current method together with Ohm's law and Kirchhoff's voltage law. A loop current is assumed to circulate around each loop in the network. Thus, in the network given in Figure 2.1, the loop current I 1 circulates around the closed loop abcd. Note that the current I 1 − I 2 is assumed to flow in the link connecting b to c. Ohm's law states that the voltage across an ideal resistor is proportional to the current flow through the resistor. For example, for the link connecting b to c

V b c = R 2 ( I 1 − I 2 )

where R 2 is the value of the resistor in the link connecting b to c. Kirchhoff's voltage law states that the algebraic sum of the voltages around a loop is zero. Applying these laws to the circuit abcd of Figure 2.1 we have

V a b + V b c + V c d = V

Substituting the product of current and resistance for voltage gives

R 1 I 1 + R 2 ( I 1 − I 2 ) + R 4 I 1 = V

We can repeat this process for each loop to obtain the following four equations:

(2.1) ( R 1 + R 2 + R 4 ) I 1 − R 2 I 2 = V ( R 1 + 2 R 2 + R 4 ) I 2 − R 2 I 1 − R 2 I 3 = 0 ( R 1 + 2 R 2 + R 4 ) I 3 − R 2 I 2 − R 2 I 4 = 0 ( R 1 + R 2 + R 3 + R 4 ) I 4 − R 2 I 3 = 0

Letting R 1 = R 4 = 1 Ω , R 2 = 2 Ω , R 3 = 4 Ω , and V = 5 volts, (2.1) becomes

4 I 1 − 2 I 2 = 5 − 2 I 1 + 6 I 2 − 2 I 3 = 0 − 2 I 2 + 6 I 3 − 2 I 4 = 0 − 2 I 3 + 8 I 4 = 0

This is a system of linear equations in four variables, I 1 , … , I 4 . In matrix notation it becomes

(2.2) 4 − 2 0 0 − 2 6 − 2 0 0 − 2 6 − 2 0 0 − 2 8 I 1 I 2 I 3 I 4 = 5 0 0 0

This equation has the form Ax = b where A is a square matrix of known coefficients, in this case relating to the values of the resistors in the circuit. The vector b is a vector of known coefficients, in this case the voltage applied to each current loop. The vector x is the vector of unknown currents. Although this set of equations can be solved by hand, the process is time consuming and error prone. Using Matlab we simply enter matrix A and vector b and use the command A\b as follows:

Figure 2.1. Electrical network.

>> A = [4 -2 0 0;-2 6 -2 0;0 -2 6 -2;0 0 -2 8];

>> b = [5 0 0 0].';

>> A\b

ans =

  1.5426

  0.5851

  0.2128

  0.0532

The sequence of operations that are invoked by this apparently simple command is examined in Section 2.3.

In many electrical networks the ideal resistors of Figure 2.1 are more accurately represented by electrical impedances. When a harmonic alternating current (AC) supply is connected to the network, electrical engineers represent the impedances by complex quantities. This is to account for the effect of capacitance and/or inductance. To illustrate this we will replace the 5 volt DC supply to the network of Figure 2.1 with a 5 volt AC supply and replace the ideal resistors R 1 , … , R 4 by impedances Z 1 , … , Z 4 . Thus (2.1) becomes

(2.3) ( Z 1 + Z 2 + Z 4 ) I 1 − Z 2 I 2 = V ( Z 1 + 2 Z 2 + Z 4 ) I 2 − Z 2 I 1 − Z 2 I 3 = 0 ( Z 1 + 2 Z 2 + Z 4 ) I 3 − Z 2 I 2 − Z 2 I 4 = 0 ( Z 1 + Z 2 + Z 3 + Z 4 ) I 4 − Z 2 I 3 = 0

At the frequency of the 5 volt AC supply we will assume that Z 1 = Z 4 = ( 1 + 0 . 5 j ) , Z 2 = ( 2 + 0 . 5 j ) , and Z 3 = ( 4 + 1 j ) , where j = − 1 . Electrical engineers prefer to use j rather than ı for − 1 . This avoids any possible confusion with I or i, which are normally used to denote the current in a circuit. Thus (2.3) becomes

( 4 + 1 . 5 j ) I 1 − ( 2 + 0 . 5 j ) I 2 = 5 − ( 2 + 0 . 5 j ) I 1 + ( 6 + 2 . 0 j ) I 2 − ( 2 + 0 . 5 j ) I 3 = 0 − ( 2 + 0 . 5 j ) I 2 + ( 6 + 2 . 0 j ) I 3 − ( 2 + 0 . 5 j ) I 4 = 0 − ( 2 + 0 . 5 j ) I 3 + ( 8 + 2 . 5 j ) I 4 = 0

This system of linear equations becomes, in matrix notation,

(2.4) ( 4 + 1 . 5 j ) − ( 2 + 0 . 5 j ) 0 0 − ( 2 + 0 . 5 j ) ( 6 + 2 . 0 j ) − ( 2 + 0 . 5 j ) 0 0 − ( 2 + 0 . 5 j ) ( 6 + 2 . 0 j ) − ( 2 + 0 . 5 j ) 0 0 − ( 2 + 0 . 5 j ) ( 8 + 2 . 5 j ) I 1 I 2 I 3 I 4 = 5 0 0 0

Note that the coefficient matrix is now complex. This does not present any difficulty for Matlab because the operation A\b works directly with both real and complex numbers. Thus

>> p = 4+1.5i; q = -2-0.5i;

>> r = 6+2i; s = 8+2.5i;

>> A = [p q 0 0;q r q 0;0 q r q;0 0 q s];

>> b = [5 0 0 0].';

>> A\b

ans =

  1.3008 - 0.5560i

  0.4560 - 0.2504i

  0.1530 - 0.1026i

  0.0361 - 0.0274i

Note that strictly we have no need to reenter the values in vector b, assuming that we have not cleared the memory, reassigned the vector b, or quit Matlab. The answer shows that currents flowing in the network are complex. This means that there is a phase difference between the applied harmonic voltage and the currents flowing.

We will now begin a more detailed examination of linear equation systems.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780123869425000023