Finding all solutions of piecewise‐linear resistive circuits using the dual simplex method

An efficient algorithm is proposed for finding all solutions of piecewise‐linear (PWL) resistive circuits using linear programming (LP). This algorithm is based on a simple test (termed the LP test) for non‐existence of a solution to a system of PWL equations in a given region. In the conventional LP test, the system of PWL equations is transformed into an LP problem, to which the simplex method is applied. However, this algorithm requires a very large number of pivotings because the simplex method is applied on many regions. In this paper, we introduce the dual simplex method to the LP test, which makes the average number of pivotings per region much smaller (less than one, for example) and makes the algorithm very efficient. By numerical examples, it is shown that the proposed algorithm could find all solutions of large‐scale problems, including those where the number of variables is 300 and the number of linear regions is 10³⁰⁰, in practical computation time. Copyright © 2002 John Wiley & Sons, Ltd.     

On simplex‐based piecewise‐linear approximations of non‐linear mappings

Simplex‐based piecewise‐linear (PWL) approximations of non‐linear mappings are needed when the robust PWL analysis is used to directly solve non‐linear equations. This paper proposes a straightforward technique for transforming the well‐known approximations into another form. This new form is computationally more efficient, since it preserves the sparse structure of the original Jacobian matrix. Furthermore, this new form of PWL approximation explicitly relates the simplex‐based PWL analysis to the conventional formulation of the Katzenelson algorithm. The proposed transform technique is also extended to treat groupwise‐separable mappings and, finally, non‐separable but sparse mappings that arise in real‐life simulation of large electronic circuits. In this paper, all these (transformed) simplex‐based PWL approximations are compared in terms of their generality and efficiency. The computational efficiency of the PWL approximation that utilizes sparsity is validated with realistic simulations. Copyright © 2005 John Wiley & Sons, Ltd.     

Digital architectures realizing piecewise‐linear multivariate functions: Two FPGA implementations

Digital architectures for the circuit realization of multivariate piecewise‐linear (PWL) functions are reviewed and compared. The output of the circuits is a digital word representing the value of the PWL function at the n‐dimensional input. In particular, we propose two architectures with different levels of parallelism/complexity. PWL functions with n = 3 inputs are implemented on an FPGA and experimental results are shown. The accuracy in the representation of PWL functions is tested through three benchmark examples, two concerning three‐variate static functions and one concerning a dynamical control system defined by a bi‐variate PWL function. Copyright © 2009 John Wiley & Sons, Ltd.     

An interval algorithm for finding all solutions of non‐linear resistive circuits

In this letter, an efficient algorithm is proposed for finding all solutions of non‐linear (not piecewise‐linear) resistive circuits. This algorithm is based on interval analysis, the dual simplex method, and the contraction methods. By numerical examples, it is shown that the proposed algorithm could find all solutions of systems of 500–700 non‐linear circuit equations in acceptable computation time. Copyright © 2004 John Wiley & Sons, Ltd.     

Speed‐up and performance evaluation of piecewise‐linear DC analysis

The good convergence properties of piecewise‐linear (PWL) DC analysis have been thoroughly discussed in many papers. This paper, in turn, concentrates on the speed of PWL DC analysis, where the boundary crossing of linear regions plays a crucial role. Fast methods are presented for performing the following boundary‐crossing computations: LU‐decomposition update, matrix‐equation solution, boundary‐crossing direction, and damping‐factor determination. Special attention is given to those PWL DC analysis methods that perform PWL modelling of the non‐linear components on the fly; an adaptive method is proposed for controlling the accuracy of PWL modelling and speeding up simulation. The computational efficiency of the accelerated PWL DC analysis is discussed and compared with that of conventional, Newton–Raphson iteration‐based, DC analysis. Finally, the performance evaluation is completed with realistic simulation examples: it is demonstrated that the speed of the accelerated PWL DC analysis is comparable with that of the conventional DC analysis. Copyright © 2006 John Wiley & Sons, Ltd.     

A unified set‐theoretic approach to the analysis of PWL resistive circuits and composite N‐ports

We consider the search for all DC solutions of resistive piecewise‐linear (PWL) circuits and the analysis of the characteristics of resistive PWL composite N‐ports. These problems are unified from a theoretical and operating point of view by introducing the so‐called N‐augmented circuit, obtained from the N‐port by closing its ports with N norators. Set‐theoretic approach is used to describe the properties of the N‐augmented circuits leading to the formulation of a general DC analysis algorithm, based on linear programming techniques. The examples at the end of the paper show some practical and efficient application of the general DC analysis algorithm. Copyright © 2010 John Wiley & Sons, Ltd.     

Synthesis of multiport resistors with piecewise‐linear characteristics: a mixed‐signal architecture

Non‐linear multiport resistors are the main ingredients in the synthesis of non‐linear circuits. Recently, a particular PWL representation has been proposed as a generic design platform (IEEE Trans. Circuits Syst.‐I 2002; 49 :1138–1149). In this paper, we present a mixed‐signal circuit architecture, based on standard modules, that allows the electronic integration of non‐linear multiport resistors using the mentioned PWL structure. The proposed architecture is fully programmable so that the unit can implement any user‐defined non‐linearity. Moreover, it is modular: an increment in the number of input variables can be accommodated through the addition of an equal number of input modules. Copyright © 2005 John Wiley & Sons, Ltd.     

Improvement of the contraction‐type LP test algorithm for finding all solutions of piecewise‐linear resistive circuits

In this letter, an effective technique is proposed for improving the computational efficiency of the contraction‐type LP test algorithm, which is an algorithm for finding all solutions of piecewise‐linear resistive circuits. Using the proposed technique, all solutions of a large‐scale problem, where the number of variables is 100 and the number of linear regions is 10¹⁰⁰, could be found in less than 10 min using a 360 MHz computer. Copyright 2001 John Wiley & Sons, Ltd.     

Towards analog implementations of PWL two‐dimensional non‐linear functions

This paper deals with the circuit implementation of non‐linear algebraic bivariate functions. The synthesis procedure is based on a piecewise‐linear approximation technique and on a corresponding circuit architecture, whose basic element is a circuit block with the input/output function y(x) = max(0; x). Some known CMOS circuit structures that can be used to obtain such a block are considered, and their main advantages and drawbacks are pointed out. The static and dynamic features of both the single circuit block and the overall architecture for two‐dimensional PWL functions are illustrated by way of examples. Copyright © 2005 John Wiley & Sons, Ltd.     

A method for the approximate synthesis of cellular non‐linear networks—Part 2: Circuit reduction

In this paper, we face the problem of model reduction in piecewise‐linear (PWL) approximations of non‐linear functions. The reduction procedure presented here is based on the PWL approximation method proposed in a companion paper and resorts to a strategy that exploits the orthonormality of basis functions in terms of a proper inner product. Such a procedure can be favourably applied to the synthesis of the resistive parts of cellular non‐linear networks (CNNs) to reduce the complexity of the resulting circuits. As an example, the method is applied to a case study concerning a CNN for image processing. Copyright © 2003 John Wiley & Sons, Ltd.     

A tutorial description of an interior point method and itsapplications to security-constrained economic dispatch

The authors deal with the use of successive linear programming (SLP) for the solution of the security-constrained economic dispatch (SCED) problem. They tutorially describe an interior point method (IPM) for the solution of linear programming (LP) problems, discussing important implementation issues that really make this method far superior to the simplex method. A study of the convergence of the SLP technique and a practical criterion to avoid oscillatory behavior in the iteration process are also proposed. A comparison of the proposed method with an efficient simplex code (MINOS) is carried out by solving SCED problems on two standard IEEE systems. The results show that the interior point technique is reliable, accurate, and more than two times as fast as the simplex algorithm     

Accelerating the transient simulation of semiconductor devices using filter‐bank transforms

Simulation of high frequency semiconductor devices, where non‐local and hot carrier transport cannot be ignored, requires solution of Poisson's equation and at least the first three moments of the Boltzmann transport equation (hydrodynamic transport model). These equations form non‐linear, coupled and time‐dependent partial differential equations. One of the most efficient solvers of such system of equations is decoupled solver. In conventional decoupled methods, the fully implicit, semi‐implicit and explicit methods are used to solve the equations. In fully or semi‐implicit schemes, the method is unconditionally stable for any Δt or for very large Δt compared to explicit scheme. Thus, these schemes are very suitable and efficient for transient simulations. But, using these techniques leads to a large system of linear equations. Here for the first time, a filter bank‐based preconditioning method is used to facilitate the iterative solution of this system. This method provides efficient preconditioners for matrices arising from discretizing of the PDEs, using finite difference techniques. Numerical results show that the condition number and iteration number are significantly reduced. The most important advantage of this preconditioner is its low computational complexity which can be reduced to O(N). Copyright © 2006 John Wiley & Sons, Ltd.     

A procedure for the computation of accurate PWL approximations of non‐linear dynamical systems

In this paper we propose a variational method to find out piecewise‐linear (PWL) approximations of non‐linear dynamical systems in view of their circuit implementations. The method is based on some significant trajectories of the dynamical system and provides reasonably accurate PWL approximations with a relatively low number of parameters. The effectiveness of the method is validated by applying it to the approximation of limit cycles (both stable and unstable) in the Bautin system. Copyright © 2006 John Wiley & Sons, Ltd.     

Chaotic system identification using Wiener‐LSSVM model

In this paper, a new method is proposed for identifying chaotic system based on a Wiener‐least squares support vector machine (Wiener‐LSSVM) model. The model consists of a linear dynamic subsystem followed by a static nonlinear function, which is represented by LSSVM in this paper. The parameters of the linear dynamic part and those of LSSVM are estimated simultaneously by solving a set of linear equations using the least squares (LS) method. The proposed method incorporates partial structure information into the identification process and does not assume that the parameters of linear dynamic part are known. On the other hand, the LS algorithm is more efficient than gradient‐descendent‐based algorithms for estimating the parameters of Wiener‐LSSVM. Three identification examples are given to validate the effectiveness of the proposed method. © 2016 Institute of Electrical Engineers of Japan. Published by John Wiley & Sons, Inc.     

A fast second‐order signal separation algorithms with on‐line capabilities

In correlation‐based signal separation algorithms, the received mixed signals are fed to a de‐coupling system designed to minimize the output cross‐correlation functions. If minimizaion is perfect, each of the system's outputs carries only one signal independent of the others. In these algorithms, the computation burden of the output cross‐correlation functions normally slows down the separation algorithm. This paper, describes a computationally efficient method for off‐line pre‐computation of the needed cross‐correlation functions. Explicit formulas have been derived for the output cross‐correlation functions in terms of the received input signals and the de‐coupling system parameters. Then, it is shown that signal separation amounts to the least‐squares solution of a system of linear equations describing these output cross‐correlation functions, evaluated over a batch of lags. Next, a fast RLS‐type adaptive algorithm is devised for on‐line signal separation. In this respect, an algorithm is derived for updating the de‐coupling parameters as data comes in. This update is achieved recursively, along the negative of the steepest descent directions of an objective cost function describing the output cross‐correlation functions over a batch of lags, subject to equal output power constraints. Illustrative examples are given to demonstrate the effectiveness of the proposed algorithms. Copyright © 2002 John Wiley & Sons, Ltd.     

A novel compact piecewise‐linear representation

A new compact MAX representation for 2‐D continuous piecewise‐linear (PWL) functions is developed in this paper. The representation is promising since it can be easily generalized into higher dimensions. We also establish the explicit functional form of basis function and demonstrate that the proposed basis function is the elementary ‘building block’ from which a fully general 2‐D PWL function can be constructed. In addition, we reveal the relationship of basis function with minimal degenerate intersection and Hinging Hyperplane, which shows that the MAX model can unify Chua's canonical expression, Li's representation, lattice PWL function and Bremann's Hinging Finding Algorithm into one common theoretical framework. Copyright © 2005 John Wiley & Sons, Ltd.     

Differential equation description and Chebyshev approximation of linear time‐invariant circuits

The approximation technology of analogue circuit functions is crucial to the computer‐aided simulation, analysis, and design automation of electronic circuits. Chebyshev polynomials and various differential equations are proposed in this paper to approximate the functions of linear time‐invariant circuits. The coefficient calculation methods of the Chebyshev expansion and the differential equation matrices are thoroughly deduced, and the construction methods employed in the functions and the actual time mapping of the linear time‐invariant circuits are presented in this paper. An example of an analogue filter verifies the effectiveness and accuracy of the proposed approximation algorithm and elaborates on the selection process of the order number and the time step length of the Chebyshev expansion according to the demanded truncation error.     

Parallel Simulation of Power Systems Transient Stability Based on Implicit Runge–Kutta Methods and W-transformation

This paper presents a novel parallel algorithm for power systems transient stability simulation based on fully implicit Runge–Kutta (IRK) method. The s-stage IRK method is used to convert the differential-algebraic system simultaneously at s different time points into a set of non-linear algebraic equations, and the algebraic system is then solved by Newton's method. By the use of the matrix factorization technique, the solution of the linear equations involved in Newton's process is divided into two parts: the first part is decoupled at s different time points, thus it is fully parallelizable in time, and the second part is solved by preconditioned generalized minimal residual method (GMRES) method, while a new preconditioning method has been proposed by using the W-transformation and double-parameters method. For test, the proposed algorithm is implemented on multiple-graphics processing units (GPUs) computing platform. The results show that the proposed algorithm is accurate and has good convergence. Moreover, the parallel algorithm implemented on multiple-GPUs computing platform achieves high parallel efficiency.     

Optimal reactive power dispatch using hybrid Nelder–Mead simplex based firefly algorithm

This paper presents a novel hybrid algorithm combining Firefly Algorithm (FA) and Nelder Mead (NM) simplex method for solving power system Optimal Reactive Power Dispatch (ORPD) problems. The ORPD is a very important aspect of power system operation and is a highly nonlinear, non-convex optimization problem, consisting of both continuous and discrete control variables. Like many other general purpose optimization methods, the original FA often traps into local optima and in order to overcome the shortcoming, in this paper, an efficient local search method called NM simplex subroutine is introduced in the internal architecture of the original FA algorithm. The proposed Hybrid Firefly Algorithm (HFA) avoids premature convergence of original FA by exploration with FA and exploitation with NM simplex. The proposed method is applied to determine optimal settings of generator voltages, tap positions of tap changing transformers and VAR output of shunt capacitors to optimize two different objective functions; such as minimization of real power loss and voltage deviations. The program is developed in Matlab and the proposed hybrid algorithm is examined on two standard IEEE test systems for solving the ORPD problems. For validation purpose, the results obtained with the proposed approach are compared with those obtained by other methods. It is observed that the proposed method has better convergence characteristics and robustness compared to the original version of FA and other existing methods. It is revealed that the proposed hybrid method is able to provide better solutions.     

An efficient algorithm for analysis of piecewise-linear resistive circuits: Driving-point and transfer characteristic plots

A new efficient algorithm is presented for finding all driving-point characteristic (DP) and transfer characteristic (TC) plots for a broad class of piecewise-linear (PWL) resistive circuits without the need for initial points for each solution branch. the piecewise-linear circuits to be considered need not be continuous nor need their linear regions be divided by grid-like hyperplanes. the computation of the new algorithm is based on zone-by-zone instead of the conventional region-by-region. Since each zone includes several regions and only one matrix inversion is needed for each zone, a significant reduction of computation can be achieved. Furthermore, the computational complexity for finding all solution branches, i.e. finding the DC operating points over the entire range of input values u, is no more than for finding all DC operating points over a single value u as far as the number of matrices needed to be inverted is concerned.