Interior-point methods applied to the AC active-reactive optimal power-flow problem using cartesian coordinates

The primal dual interior point methods are developed to the AC active and reactive optimal power flow problem. The representation of the tensions through cartesian coordinates is adopted, once the Hessian is constant and the Taylor expansion is accurate for the second order term. The advantage of working with polar coordinates, that easily model the tension magnitudes, lose importance due to the efficient treatment of inequalities proportionated by the interior point methods. Before the application of the method, the number of variables of the problem is reduced through the elimination of free dual variables. This elimination does not modify the sparse pattern of the problem. The linear system obtained can be further reduced to the dimension of twice the number of buses also with minor changes in the sparse structure of the matrices involved. Moreover, the final matrix is symmetric in structure. This feature can be exploited reducing the computational effort per iteration. Computational experiments for IEEE system problems are presented for several starting point strategies showing the advantages of the proposed approach. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A novel approach to solve linear systems arising from BEM using fast wavelet transforms

This paper uses Daubechies orthogonal wavelets to change dense and fully populated matrices of boundary element method (BEM) systems into sparse and semi‐banded matrices. Then a novel algorithm based on hierarchical nature of multiresolution analysis is introduced to solving resultant sparse linear systems. This algorithm decomposes NS‐form of transformed parent matrix into descendant systems with reduced sizes and solves them iteratively using GMRES algorithm. Both parts, changing dense matrices to sparse systems and the novel solver, can be added as a black box to the existing BEM codes. Transforming matrices into wavelet space needs less time than saved by solving sparse large systems. Numerical results with a precise study on sensitivity of solution for physical variables to the thresholding parameter, and savings in computer time and memory are presented. Also, the suitable value for thresholding parameter is recommended for elasticity problems. The results indicate that the proposed method is efficient for large problems. Copyright © 2009 John Wiley & Sons, Ltd.     

Spectral estimates for saddle point matrices arising in weak constraint four‐dimensional variational data assimilation

We consider the large sparse symmetric linear systems of equations that arise in the solution of weak constraint four‐dimensional variational data assimilation, a method of high interest for numerical weather prediction. These systems can be written as saddle point systems with a 3 × 3 block structure but block eliminations can be performed to reduce them to saddle point systems with a 2 × 2 block structure, or further to symmetric positive definite systems. In this article, we analyse how sensitive the spectra of these matrices are to the number of observations of the underlying dynamical system. We also obtain bounds on the eigenvalues of the matrices. Numerical experiments are used to confirm the theoretical analysis and bounds.     

Hyperbolic conservation laws with stiff relaxation terms and entropy

We study the limiting behavior of systems of hyperbolic conservation laws with stiff relaxation terms. Reduced systems, inviscid and viscous local conservation laws, and weakly nonlinear limits are derived through asymptotic expansions. An entropy condition is introduced for N × N systems that ensures the hyperbolicity of the reduced inviscid system. The resulting characteristic speeds are shown to be interlaced with those of the original system. Moreover, the first correction to the reduced system is shown to be dissipative. A partial converse is proved for 2 × 2 systems. This structure is then applied to study the convergence to the reduced dynamics for the 2 × 2 case. © 1994 John Wiley & Sons, Inc.     

A nested dissection approach for sparse matrix partitioning

We consider how to partition and distribute sparse matrices among processors to reduce communication cost in sparse matrix computations, in particular, sparse matrix-vector multiplication. We consider 2d distributions, where the distribution is not constrained to just rows or columns. We present a new model and an algorithm based on vertex separators and nested dissection. Preliminary numerical results for sparse matrices from real applications indicate the new method performs consistently better than traditional 1d partitioning and is often also better than current 2d methods. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Proper orthogonal decomposition in sparse optimal control of some reaction diffusion equations using model predictive control

We investigate optimal sparse control problems for reaction diffusion equations with non-monotonous cubic non-linearities. In particular, we consider the Schlöl equation as well as the FitzHugh-Nagumo system. In these models, the solutions form pattern of traveling wave fronts or spiral waves. To control them turns out to be very challenging and computational difficult. The needed computational times are enormous. The use of sparse optimal control techniques was surprisingly very helpful. On the one hand the optimal control becomes sparse and on the other hand we achieve our control goals with satisfying accuracy for much less computational time then before. Trying to decrease it even more by POD model reduction does not work sufficiently well since too many POD modes are needed to approximate the solutions satisfactorily. Our second approach is the application of model predictive controls. This technique performs very well for the control aim of following a desired trajectory. An additional use of POD model reduction for each - now very small - time horizon yields even better results in computational time with a marginal loss of precession. This result holds for optimal controls as well as for optimal sparse controls. (© 2014 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A sparse grid method for the Navier–Stokes equations based on hyperbolic cross

A sparse grid method for the time‐dependent Navier–Stokes equations based on hyperbolic cross approximation is considered in this article. Subsequent truncation of the associated series expansion results in a sparse grid discretization. Stability and convergence of the fully discrete sparse grid method are established. Finally, the numerical experiment is presented to show the effectiveness of this sparse grid method. Copyright © 2013 John Wiley & Sons, Ltd.     

Mixed two‐grid finite difference methods for solving one‐dimensional and two‐dimensional Fitzhugh–Nagumo equations

The aim of this paper is to propose mixed two‐grid finite difference methods to obtain the numerical solution of the one‐dimensional and two‐dimensional Fitzhugh–Nagumo equations. The finite difference equations at all interior grid points form a large‐sparse linear system, which needs to be solved efficiently. The solution cost of this sparse linear system usually dominates the total cost of solving the discretized partial differential equation. The proposed method is based on applying a family of finite difference methods for discretizing the spatial and time derivatives. The obtained system has been solved by two‐grid method, where the two‐grid method is used for solving the large‐sparse linear systems. Also, in the proposed method, the spectral radius with local Fourier analysis is calculated for different values of h and Δt. The numerical examples show the efficiency of this algorithm for solving the one‐dimensional and two‐dimensional Fitzhugh–Nagumo equations. Copyright © 2016 John Wiley & Sons, Ltd.     

Short communication: Dimensionality reduction of curvelet sparse regularizations in limited angle tomography

We investigate the reconstruction problem for limited angle tomography. Such problems arise naturally in applications like digital breast tomosynthesis, dental tomography, etc. Since the acquired tomographic data is highly incomplete, the reconstruction problem is severely ill-posed and the traditional reconstruction methods, such as filtered backprojection (FBP), do not perform well in such situations. To stabilize the inversion we propose the use of a sparse regularization technique in combination with curvelets. We argue that this technique has the ability to preserve edges. As our main result, we present a characterization of the kernel of the limited angle Radon transform in terms of curvelets. Moreover, we characterize reconstructions which are obtained via curvelet sparse regularizations at a limited angular range. As a result, we show that the dimension of the limited angle problem can be significantly reduced in the curvelet domain. (© 2011 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Implementación eficiente de una formulación semirrecursiva para la dinámica de sistemas multicuerpo de gran tamaño

This article shows an efficient implementation of a dynamic semi-recursive formulation for large and complex multibody system simulations, with interesting applications in the automotive field and especially with industrial vehicles. These systems tend to have a huge amount of kinematic constraints, becoming usual the presence of redundant but compatible systems of equations. The maths involved in the solution of these problems have a high computational cost, making very challenging to achieve real-time simulations.In this article, two implementations to increase the efficiency of these computations will be shown. The difference between them is the way they consider the Jacobian matrix of the constraint equations. The first one treats this matrix as a dense one, using the BLAS functions to solve the system of equations. The second one takes into account the sparse pattern of the Jacobian matrix, introducing the sparse function MA48 from Harwell.Both methodologies have been applied on two multibody system models with different sizes. The first model is a vehicle IVECO DAILY 35C15 with 17 degrees of freedom. The second one is a semi-trailer truck with 40 degrees of freedom. Taking as a reference the standard C/C + + implementation, the efficiency improvements that have been achieved using dense matrices (BLAS) have been of 15% and 50% respectively. The results in the first model have not improved significantly by using sparse matrices, but in the second one, the times with sparse matrices have been reduced 8% with respect to the BLAS ones.     

A multigrid compact finite difference method for solving the one‐dimensional nonlinear sine‐Gordon equation

The aim of this paper is to propose a multigrid method to obtain the numerical solution of the one‐dimensional nonlinear sine‐Gordon equation. The finite difference equations at all interior grid points form a large sparse linear system, which needs to be solved efficiently. The solution cost of this sparse linear system usually dominates the total cost of solving the discretized partial differential equation. The proposed method is based on applying a compact finite difference scheme of fourth‐order for discretizing the spatial derivative and the standard second‐order central finite difference method for the time derivative. The proposed method uses the Richardson extrapolation method in time variable. The obtained system has been solved by V‐cycle multigrid (VMG) method, where the VMG method is used for solving the large sparse linear systems. The numerical examples show the efficiency of this algorithm for solving the one‐dimensional sine‐Gordon equation. Copyright © 2014 John Wiley & Sons, Ltd.     

Incomplete Gröbner basis as a preconditioner for polynomial systems

Precondition plays a critical role in the numerical methods for large and sparse linear systems. It is also true for nonlinear algebraic systems. In this paper incomplete Gröbner basis (IGB) is proposed as a preconditioner of homotopy methods for polynomial systems of equations, which transforms a deficient system into a system with the same finite solutions, but smaller degree. The reduced system can thus be solved faster. Numerical results show the efficiency of the preconditioner.     

Indefinitely preconditioned inexact Newton method for large sparse equality constrained non-linear programming problems

An inexact Newton algorithm for large sparse equality constrained non-linear programming problems is proposed. This algorithm is based on an indefinitely preconditioned smoothed conjugate gradient method applied to the linear KKT system and uses a simple augmented Lagrangian merit function for Armijo type stepsize selection. Most attention is devoted to the termination of the CG method, guaranteeing sufficient descent in every iteration and decreasing the number of required CG iterations, and especially, to the choice of a suitable preconditioner. We investigate four preconditioners, which have 2 × 2 block structure, and prove theoretically their good properties. The efficiency of the inexact Newton algorithm, together with a comparison of various preconditioners and strategies, is demonstrated by using a large collection of test problems. © 1998 John Wiley & Sons, Ltd.     

Sparse Data Representation of Random Fields

Mathematical models with uncertainties are often described by stochastic partial differential equations (SPDEs) with multiplicative noise. The coefficients, the right-hand side, the boundary conditions are modelled by random fields. As a result the solution is also a random field. We offer to use the Karhunen-Loève expansion (KLE) to compute a sparse data format for the fast generation and representation of these random fields. The KLE of a random field requires the solution of a large eigenvalue problem. Usually it is solved by a Krylov subspace method with a sparse matrix approximation. We demonstrate the use of both, the sparse hierarchical matrix format as well as the low-rank Kronecker tensor format. (© 2009 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Model Reduction Methods for Solving Symmetric Rational Eigenvalue Problems

We consider large and sparse rational eigenproblems where the rational term is of low rank compared to the dimension of the problem. Exploiting model‐order reduction techniques the dimension can be reduced considerably, and problems of this type can be solved very efficiently. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

The curvelet representation of wave propagators is optimally sparse

This paper argues that curvelets provide a powerful tool for representing very general linear symmetric systems of hyperbolic differential equations. Curvelets are a recently developed multiscale system [7, 9] in which the elements are highly anisotropic at fine scales, with effective support shaped according to the parabolic scaling principle width ≈ length² at fine scales. We prove that for a wide class of linear hyperbolic differential equations, the curvelet representation of the solution operator is both optimally sparse and well organized.

• It is sparse in the sense that the matrix entries decay nearly exponentially fast (i.e., faster than any negative polynomial) and
• well organized in the sense that the very few nonnegligible entries occur near a few shifted diagonals.

Indeed, we show that the wave group maps each curvelet onto a sum of curveletlike waveforms whose locations and orientations are obtained by following the different Hamiltonian flows—hence the diagonal shifts in the curvelet representation. A physical interpretation of this result is that curvelets may be viewed as coherent waveforms with enough frequency localization so that they behave like waves but at the same time, with enough spatial localization so that they simultaneously behave like particles. © 2005 Wiley Periodicals, Inc.     

Solution of sparse quasi-square rectangular systems by Gaussian elimination

We present a general method for the linear least-squares solutionof overdetermined and underdetermined systems. The method isparticularly efficient when the coefficient matrix is quasi-square,that is when the number of rows and number of columns is almostthe same. The numerical methods for linear least-squares problemsand minimum-norm solutions do not generally take account ofthis special characteristic. The proposed method is based onLU factorization of the original quasi-square matrix A, assumingthat A has full rank. In the overdetermined case, the LU factorsare used to compute a basis for the null space of A^T. The right-handside vector b is then projected onto this subspace and the least-squaressolution is obtained from the solution of this reduced problem.In the case of underdetermined systems, the desired solutionis again obtained through the solution of a reduced system.The use of this method may lead to important savings in computationaltime for both dense and sparse matrices. It is also shown inthe paper that, even in cases where the matrices are quite small,sparse solvers perform better than dense solvers. Some practicalexamples that illustrate the use of the method are included.     

A Schur complement approach to preconditioning sparse linear least-squares problems with some dense rows

The effectiveness of sparse matrix techniques for directly solving large-scale linear least-squares problems is severely limited if the system matrix A has one or more nearly dense rows. In this paper, we partition the rows of A into sparse rows and dense rows (A_s and A_d) and apply the Schur complement approach. A potential difficulty is that the reduced normal matrix AsTA_s is often rank-deficient, even if A is of full rank. To overcome this, we propose explicitly removing null columns of A_s and then employing a regularization parameter and using the resulting Cholesky factors as a preconditioner for an iterative solver applied to the symmetric indefinite reduced augmented system. We consider complete factorizations as well as incomplete Cholesky factorizations of the shifted reduced normal matrix. Numerical experiments are performed on a range of large least-squares problems arising from practical applications. These demonstrate the effectiveness of the proposed approach when combined with either a sparse parallel direct solver or a robust incomplete Cholesky factorization algorithm.     

An algebraic multifrontal preconditioner that exploits the low‐rank property

We present an algebraic structured preconditioner for the iterative solution of large sparse linear systems. The preconditioner is based on a multifrontal variant of sparse LU factorization used with nested dissection ordering. Multifrontal factorization amounts to a partial factorization of a sequence of logically dense frontal matrices, and the preconditioner is obtained if structured factorization is used instead. This latter exploits the presence of low numerical rank in some off‐diagonal blocks of the frontal matrices. An algebraic procedure is presented that allows to identify the hierarchy of the off‐diagonal blocks with low numerical rank based on the sparsity of the system matrix. This procedure is motivated by a model problem analysis, yet numerical experiments show that it is successful beyond the model problem scope. Further aspects relevant for the algebraic structured preconditioner are discussed and illustrated with numerical experiments. The preconditioner is also compared with other solvers, including the corresponding direct solver. Copyright © 2015 John Wiley & Sons, Ltd.