A study on the tie‐set graph theory and network flow optimization problems

Aiming at establishing a firm basic theory to ring‐based information network management systems, our paper proposes a tie‐set graph theory. We define a binary vector representing a tie‐set in a biconnected undirected graph G=(V,E) as a tie‐set vector. The set of tie‐set vectors forms a vector space over the proposed law of composition, then a basis of the vector space, μ linear independent tie‐set vectors, is defined as a tie‐set basis. The essential key concept in our theory is a tie‐set graph, which has a one‐to‐one correspondence to a tie‐set basis and represents a relation between two tie‐set vectors of the basis. Some important properties of tie‐set graphs and their application to survivable mesh networks in modern high‐speed backbone networks are also presented. Furthermore, as a general approach to network flow optimization problems, tie‐set flow vector space is proposed based on the tie‐set graph theory. A distributed algorithm for the network flow optimization problems and its application are also presented in this paper. Copyright © 2004 John Wiley & Sons, Ltd.     

Rearrangeability of 7-stage 16 × 16 shuffle exchange networks

It has long been an outstanding conjecture that any (2n − 1)-stage shuffle exchange network (Omega network) is rearrangeable for 2 ⁿ × 2 ⁿ . Many researchers have failed to prove this conjecture, including a recent one established by Hasan. However, nobody has pointed out its fallacy. Therefore, as one of the objectives, this paper shall clarify this fact. Since the case of n = 3 has been proven by many researchers [1,2], this paper uses a constructive approach to prove that when n = 4, the 7-stage 16 × 16 shuffle exchange network is also rearrangeable. The paper also presents the model of a balanced tree to avoid internal conflict, the representation of permutations using a connection graph and loop graph, and the concepts of symmetry graph and identical transform. Based on graphic composition and bipartition, the permutations 16 × 16 are divided into five classes, with five assignment algorithms proposed. These algorithms are simpler, clearer and easier to program. The techniques used for n = 4 may provide hints for the general case of n > 4. __________ Translated from Acta Electronica Sinica, 2007, 35(10): 1875–1885 [译自: 电子学报]     

Hilbert Graph: An Expandable Interconnection for Clusters

This paper presents a new interconnection network inspired by chordal graphs and the small-world phenomenon, with an emphasis in providing an incrementally expandable network with a fixed degree and a small diameter. Whereas most small-world graphs are constructed by a random process, the proposed graphs are completely deterministic and regular. The Hilbert graph is constructed by a number of nodes laid down in a Hilbert curve to which a number of additional edges forming an extended mesh are incorporated. It is shown that the resulting structures are quasi planar, and posses the same cutwidth complexity of a two dimensional torus. Furthermore the Hilbert graph posses the same fixed degree and incrementally expandable properties of the torus and mesh; however it is shown that the Hilbert graph has a much larger tolerance to an increase in traffic, and can therefore be expanded to much larger systems than the mesh or torus. In particular it is shown that with an equal congestion, the number of nodes on a Hilbert network is at least O(N^2.477) larger than that of a torus. Furthermore, while broadcast in the two dimensional torus takes at least N^1/2 steps, it is shown that the same operation can be accommodated in O(N^1/4) steps in a Hilbert graph.     

配电网负荷均衡的网络分割算法

随着配电网规模的不断扩大 ,配电网网络重构算法的实时性越来越难以满足工程实用化的要求。而网络重构的结果其实是将一个配电网分割成几部分 ,各部分通过常开的联络开关相连。基于此 ,提出了配电网负荷均衡的新算法———网络分割算法。该算法将负荷均衡作为一个网络优化问题 ,利用配电网的一种新模型———分层拓扑模型 ,将全局最优问题转为多阶段分割问题 ;同时 ,充分利用配电网负荷均衡的特点 ,通过寻找源点分支负荷大于负荷平均值的下确界负荷和小于负荷平均值的上确界负荷的方法 ,实现了配电网的负荷全局最优均衡。算例的仿真结果说明了该算法的正确、有效和快速。     

A generalized theorem of Reichert for biquadratic minimum functions

This paper is concerned with a generalized theorem of Reichert for biquadratic minimum functions, which states that any biquadratic minimum function realizable as the impedance of networks with n reactive elements and an arbitrary number of resistors can be realized with n reactive elements and two resistors. First, a series of constraints on networks realizing minimum functions are presented. Furthermore, by discussing the possible resistor edges incident with vertices of the reactive‐element graphs, it is proved that any minimum function realizable as the impedance of networks with three reactive elements and an arbitrary number of resistors can be realized with three reactive elements and two resistors, from which the validity of the case of n = 3 follows. Similarly, the validity of the case of n = 4 is proved. Together with the Bott–Duffin realizations, the generalized theorem of Reichert for biquadratic minimum functions is finally proved. The results of this paper are motivated by passive mechanical control. Copyright © 2016 John Wiley & Sons, Ltd.     

A new feasible method for the design of stray-insensitive optimum switched capacitor networks

On the basis of signal flow graphs a general method is described for the design of stray-insensitive switched capacitor networks. to be able to choose the optimum one, the method involves the search of all possible topologies for the specially formed signal flow graph of the given z-domain transfer function and is easily implemented by digital computer.     

Analytic solutions for some basic problems in electricity involving intersecting sphere and circular cylinder pairs

The method of electrical inversion in classical electrostatics is employed to obtain exact solutions for basic electrostatic problems pertaining to overlapping spheres/cylinders. The problems considered here include (1) a pair of overlapping conducting spheres, intersecting at a vertex angle ??/n, n an integer, placed in a constant potential field; (2) a pair of infinitely long conducting circular cylinders, intersecting at a vertex angle ??/n, n an integer, placed in a uniform field; and (3) a composite hybrid geometry consisting of two orthogonally intersecting infinitely long circular cylinders whose boundary is a combination of conducting and dielectric surfaces (with mixed boundary conditions) submerged in a uniform field. Applying the basic idea of Kelvin??s inversion repeatedly, solutions for the electric potentials are derived in each case. An exact expression for the capacitance in terms of the two radii, center-to-center distance, and the vertex angle is found for the twin sphere geometry. The capacity is then used to find the steady-state rate coefficient of a perfectly absorbing body placed in a thermally conducting environment of lower temperature. The equipotentials are plotted using the exact solutions of the two-dimensional problems and their features are discussed as well. The simple method illustrated here can be useful both as a teaching tool and as a building block for further computations.     

Effect of vanadium doping on ferroelectric and electrical properties of Bi3.25La0.75Ti3O12 thin film

Bi_3.25La_0.75Ti₃O₁₂ (BLT) and V-doped BLT (BLTV) thin films were prepared on Pt/Ti/SiO₂/Si substrates by a pulsed laser deposition method. The effects of V doping on ferroelectric and electrical properties were investigated by polarization-electric field hysteresis loops and leakage current-voltage measurements. BLTV single phases were confirmed by X-ray diffraction. Remnant polarization was increased and the leakage current density was decreased by V doping. The leakage current density of BLT thin films suddenly increased at 100 kV/cm while that of BLTV thin films increased at the higher electric field of 160 kV/cm. The power law relationship J α Eⁿ of current density vs. applied electric field is estimated to be J αE^2.0 for BLT and J αE^1.0 for BLTV thin films. The leakage current of the BLT/Pt junction can be explained by space-charge-limited current. However, that of the BLTV/Pt junction was characterized by the Schottky emission behavior.     

A study of the least mean p‐th adaptive notch filter

In this paper we propose a least mean p‐th adaptive notch filter that has a cost function of E[e^p(n)], where e(n) is the estimation error. The structure of the adaptive filter is a tandem connection of the second‐order adaptive notch filter with an all‐pass filter. In general, the bandwidth of the notch filter should be extremely small from the theoretical and practical viewpoints. However, the convergence speed of the weight becomes slow if the bandwidth is reduced. The transfer function of the notch filter has the following special characteristic, that is, zero in the center frequency and unity in other frequencies. The equivalent broad bandwidth can be obtained when the cost function is chosen as E[e^p(n)]. Higher convergence speed and excellent stationary performance are obtained using the combination of E[e^p(n)]. Finally, the convergence performance of the estimation accuracy is verified by the computer simulation. © 2004 Wiley Periodicals, Inc. Electr Eng Jpn, 150(3): 46–53, 2005; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/eej.20045     

PRESS-based proton single-voxel spectroscopy and spectroscopic imaging with very short echo times using asymmetric RF pulses

Modified point-resolved spectroscopy (PRESS) sequences for single voxel spetroscopy (MRS) and spectroscopic imaging (SI) with very short echo time (T _E ) are described using asymmetric radio-frequency (RF) pulses as well as an optimized design and timing of the PRESS sequence. The proposed sequences were implemented on a standard 4.7 T imaging system yielding a T _E of 6.0 ms only. Simulations and experimental data measured on phantoms and the rat brain in vivo are presented for MRS and SI showing a high signal-to-noise ratio and hardly any phase distortions caused by J-coupling.     

The topological foundations of electrical networks — complete models

The aim of this paper is to identify the topological entities underlying the construction of a complete (not reduced) network model. Consider an active network as a pair of physically different structures, i.e. a ‘dead network’ and an ‘excitation’. First, we define the general structure of the excitation which can be applied to a dead network; then the graphs G_a and G of the active and dead networks, respectively, are introduced. It is shown that, if a complete network model is to be constructed, the topological relations among the voltages and those among the currents of the network elements must be written choosing maximal independent sets of loops and cut-sets of G_a. It is successively pointed out that the graph G can be obtained from G_a by means of a reduction operation, and the topological entities of G corresponding to the loops and to the cut-sets of G_a are singled out. It has been found that a complete model of an electric network implies the use of four topological entities defined on the set of G-edges, i.e. the closed path, the open path, the cut-set and the pseudo-cut, together with two topological entities defined on a maximal set of independent vertex couples of G, i.e. the ‘junction pair’ extreme of an open path and the ‘family of independent node couples’ split by a cut-set. Furthermore the different reference frames and the relative topological matrix transformations which allow a complete model of the network to be built up are singled out and discussed.     

Solving the m‐way graph partitioning problem using a genetic algorithm

The m‐way graph partitioning problem is of central importance in combinatorial optimization. It has many important applications in fields such as VLSI circuit design, task allocation in distributed computing systems, and network partitioning. In this paper, we propose an efficient genetic algorithm to solve this problem. The proposed method searches a large solution space and finds the best possible solution by adjusting the intensification and diversification automatically during the optimization process. The proposed method is tested on a large number of instances and compared with some existing algorithms. The experimental results show that the proposed algorithm is superior to its competitors in terms of computation time and solution quality. © 2011 Institute of Electrical Engineers of Japan. Published by John Wiley & Sons, Inc.     

A genetic algorithm for the optimal sequential partitioning problem

The optimal sequential problem is defined as the problem of finding the minimum cost partition of the nodes of a directed acyclic graph into subsets of a given size, subject to the constraint that the precedence relationships among the elements are satisfied. A heuristic algorithm based on tabu search has been proposed for this problem [2]. However, there is a tendency for the solutions obtained by tabu search to become trapped in bad local optima in parallel graphs with random edge costs. In this paper we present a genetic algorithm for the optimal sequential partitioning problem. We develop an effective two‐point partial order crossover satisfying sequential conditions, which preserve better blocks that have a larger sum of edge costs. In this crossover we introduce the roulette selection method to escape local optima. We also assess the effectiveness of the algorithm. The results show that this proposed algorithm outperforms any other algorithm using tabu search in terms of solution quality. © 2001 Scripta Technica, Electr Eng Jpn, 135(4): 43–51, 2001     

Implementing extra element theorem using nullor approach

This letter presents a method of implementing the extra element theorem (EET) on the computer by using the nullor method. The EET involves the calculation of two driving‐point impedances (dpi's), namely the conventional dpi, Z_d, and the null dpi, Z_n. The proposed method is used mainly for calculating Z_n. The method is simplified by representing any given circuit using exclusively RC‐nullor and R‐nullor equivalent circuits, thereby permitting the use of a single (parallel) version of the EET. The proposed method is applied to the linearized boost converter model to derive the fragmented version of the duty‐ratio‐to‐output transfer function. Copyright © 1999 John Wiley & Sons, Ltd.     

含柔性多状态开关的配电网分区方法

柔性多状态开关是一种新型智能配电装置。结合柔性多状态开关的功能特点,提出了含柔性多状态开关的配电网分区条件。以多层图分割理论框架为基础,提出了由粗化、分区和还原阶段构成的分区方法。在粗化过程中,提出了基于最短电气距离的粗化方法,使用贪婪图生长算法完成初始分区,并在还原阶段提出了基于路径搜索的还原方法。分区方法不仅能够优化配电网的运行指标,还能够提高配电网的可控性和灵活性。通过IEEE 118节点配电网算例对所述分区方法进行了说明和验证,并结合柔性多状态开关的调控对分区效果进行了进一步分析。结果表明,该方法能够改善配电网的日均馈线负载均衡度,并能够和柔性多状态开关的调控相配合,进一步改善配电网每一时刻的馈线负载均衡度和电压分布。     

A method of calculation of transient electromagnetic field in non-linear ferromagnetic medium

Contents The paper presents a method of calculation the transient electromagnetic field in ferromagnetic material, taking into account the real characteristics of magnetization. Using the difference method, the spatial-temporal distributions of electromagnetic field have been calculated in result of solving the non-linear partial differential equation for electric field E (in space (x, t)). For the difference diagram assumed for approximation of the differential equation, the conditions of stability and convergence, and the condition of obtaining the minimum error of approximation, have been determined.

---

Berechnungsmethode des nichtstationären elektromagnetischen Feldes im ferromagnetischen Medium

Übersicht Es wird eine Berechnungsmethode des nichtstationären elektromagnetischen Feldes unter Berücksichtigung der realen Magnetisierungskurven beschrieben, in der die nichtlineare Differentialgleichung des elektrischen FeldesE (im Raum (x, t)) gelöst und die zeitliche und räumliche Verteilung des elektromagnetischen Feldes dargestellt wird. Die Bedingungen der Stabilität, der Konvergenz und des minimalen Approximationsfehlers für die angenommene Differentialgleichung werden auch bestimmt.

---

List of principal symbols T+E _j ⁿ =E _j+1 ⁿ shift operator - T–E _j ⁿ =E _j–1 ⁿ shift operator - E electric field strength - H magnetic field strength - B magnetic flux density - t time - conductivity - _st magnetic static permeability - _d magnetic dynamic permeability - (x, t) space in which solution is searched - _h (x, t) grid space - L[·] differential operator - L _h [·] operator of difference method - R _h [·] absolute error of approximation - r _h [·] relative error of approximation - T time constant - S _n quadratic form - x increment alongx-axis - t increment alongt-axis     

Processing and Properties of Ferroelectric Pb(Zr,Ti)O3/Silicon Carbide Field-Effect Transistor

Metal-ferroelectric-(insulator)-semiconductor MF(I)S structures have been fabricated and the properties of pulsed laser-deposited PZT/Al₂O₃ gate stacks have been studied on n- and p-type 4H-SiC. Among several polytypes of SiC, 4H-SiC is considered as the most attractive one because of its wider bandgap (E _g ? 3.2 eV) as well as higher and more isotropic bulk mobility than other polytypes. Single PZT phase without a preferred orientation was confirmed by x-ray diffraction. The interface trap densities N _IT, fixed oxide charges Q _F, and trapped oxide charges Q _HY have been estimated by C-V curves with and without photo-illuminated measurements at room temperature. It is found that the charge injection from SiC is the dominant mechanism for C-V hysteresis. Importantly, with PZT/Al₂O₃ gate stacks, superior C-V characteristics with negligible sweep rate dependence and negligible time dependence under the applied bias were obtained compared to PZT directly deposited on SiC. The MFIS structures exhibited very stable capacitance-voltage C-V loops with low conductance (<0.1 mS/cm², tan δ ～ 0.0007 at 400 kHz) and memory window as wide as 10 V, when 5 nm-thick Al₂O₃ was used as a high bandgap (E _g ～ 9 eV) barrier buffer layer between PZT (E _g ～ 3.5 eV) and SiC (E _g ～ 3.2 eV). The structures have shown excellent electrical properties promising for the gate stacks as the SiC field-effect transistors (FETs). Depletion mode transistors were prepared by forming a Pb(Zr_0.52Ti_0.48)O₃/Al₂O₃ gate stack on 4H-SiC. Based on this structure, ferroelectric Pb(Zr,Ti)O₃ (PZT) thin films have been integrated on 4H-silicon carbide (SiC) in a SiC field-effect transistor process. Nonvolatile operation of ferroelectric-gate field-effect transistors in silicon carbide (SiC) is demonstrated.     

Orthogonal nonnegative learning for sparse feature extraction and approximate combinatorial optimization

Nonnegativity has been shown to be a powerful principle in linear matrix decompositions, leading to sparse component matrices in feature analysis and data compression. The classical method is Lee and Seung’s Nonnegative Matrix Factorization. A standard way to form learning rules is by multiplicative updates, maintaining nonnegativity. Here, a generic principle is presented for forming multiplicative update rules, which integrate an orthonormality constraint into nonnegative learning. The principle, called Orthogonal Nonnegative Learning (ONL), is rigorously derived from the Lagrangian technique. As examples, the proposed method is applied for transforming Nonnegative Matrix Factorization (NMF) and its variant, Projective Nonnegative Matrix Factorization (PNMF), into their orthogonal versions. In general, it is well-known that orthogonal nonnegative learning can give very useful approximative solutions for problems involving non-vectorial data, for example, binary solutions. Combinatorial optimization is replaced by continuous-space gradient optimization which is often computationally lighter. It is shown how the multiplicative updates rules obtained by using the proposed ONL principle can find a nonnegative and highly orthogonal matrix for an approximated graph partitioning problem. The empirical results on various graphs indicate that our nonnegative learning algorithms not only outperform those without the orthogonality condition, but also surpass other existing partitioning approaches.     

Local Discontinuous Galerkin Methods for Moment Models in Device Simulations: Formulation and One Dimensional Results

We report our preliminary work in applying the local discontinuous Galerkin (LDG) finite element method to solve time dependent and steady state moment models, such as the hydrodynamic (HD) models and the energy transport (ET) models, for semiconductor device simulations, in which both the first derivative convection terms and second derivative diffusion (heat conduction) terms exist and are discretized by the discontinuous Galerkin (DG) method and the LDG method respectively. The potential equation for the electric field is also discretized by the LDG method, thus the numerical tool is based on a unified discontinuous Galerkin methodology for different components and is hence potentially viable for efficient h-p adaptivity and parallel implementation. One dimensional n⁺-n-n⁺ diode is simulated in this paper using the HD and ET models and comparison is made with earlier finite difference Essentially Non-Oscillatory (ENO) simulation results.     

A graph theoretical interpretation of nonsymmetric permutation on sparse matrices

In the tableau approach to large-electrical-network analysis, as well as in structure analysis, the finite-element method, linear programming etc., a very sparse linear algebraic set of equations Ax = b has to be solved repeatedly. To efficiently solve the system via Gaussian elimination, an optimization problem has to be faced: the selection of a pivot strategy to maintain the sparsity of the matrix A . It is possible also to follow a different strategy to fully exploit the sparsity of A , i.e. to transform A into an equivalent but more convenient form. Both of these problems have been studied and partially solved by means of directed graphs associated with A when symmetric permutations on A are allowed. In this paper, a graph theoretical interpretation has been given to nonsymmetric permutations on A , which can be considered a fundamental step towards the solution of the above-mentioned optimization problems. This interpretation is obtained through decomposition theorems on nonsymmetric permutations, correspondence theorems between column (row) permutations and topological operations on a directed graph representing A .