The Experts below are selected from a list of 202236 Experts worldwide ranked by ideXlab platform
Dan Jiao - One of the best experts on this subject based on the ideXlab platform.
-
accuracy controlled direct integral equation solver of Linear Complexity with change of basis for large scale interconnect extraction
International Microwave Symposium, 2018Co-Authors: Dan JiaoAbstract:In this paper, we develop a new Linear-Complexity direct solver for large-scale integral equation based interconnect extraction. The new solver possesses not only explicitly controlled accuracy, but also a change of cluster basis to efficiently account for the updates to the original matrix during the direct solution procedure. Comparisons with state-of-the-art direct solvers have demonstrated a much reduced CPU run time of the new solver as well as a significantly improved accuracy, which is also well controlled. Rapid and accurate direct solutions of millions of unknowns have been obtained on a single CPU core.
-
Linear Complexity direct integral equation solver with explicit accuracy control for large scale interconnect extraction
2018 International Applied Computational Electromagnetics Society Symposium (ACES), 2018Co-Authors: Dan JiaoAbstract:In this paper, we develop new Linear-Complexity direct matrix solutions for large-scale integral equation based interconnect extraction, including both factorization and inversion algorithms. These algorithms have explicitly controlled accuracy, while taking less CPU time than existing direct solvers. Rapid direct solutions of millions of unknowns have been obtained on a single CPU core with explicit accuracy control.
-
Linear Complexity direct finite element solver based shape design of electromagnetic structures
International Symposium on Antennas and Propagation, 2016Co-Authors: Bangda Zhou, Dan JiaoAbstract:In this work, we show how the shape synthesis of electromagnetic structures can be converted to an equivalent inverse problem, and subsequently solved by a Linear-Complexity direct finite-element solver without the need for an optimizer.
-
direct finite element solver of Linear Complexity for large scale 3 d electromagnetic analysis and circuit extraction
IEEE Transactions on Microwave Theory and Techniques, 2015Co-Authors: Bangda Zhou, Dan JiaoAbstract:In this paper, we develop a Linear-Complexity direct finite-element solver for the electromagnetic analysis of general 3-D problems containing arbitrarily shaped lossy or lossless conductors in inhomogeneous materials. Both theoretical analysis and numerical experiments have demonstrated the solver’s Linear Complexity in CPU time and memory consumption with prescribed accuracy satisfied. The proposed direct solver has successfully analyzed an industry product-level full package involving over 22.8488 million unknowns in approximately 16 h on a single core running at 3 GHz. It has also rapidly solved large-scale antenna arrays of over 73 wavelengths with 3600 antenna elements whose number of unknowns is over 10 million. The proposed direct solver has been compared with the finite-element methods that utilize the most advanced direct sparse solvers and a widely used commercial iterative finite-element solver. Clear advantages of the proposed solver in time and memory Complexity, as well as computational efficiency, have been demonstrated.
-
Linear Complexity direct finite element solver for irregular meshes and matrices without mesh
International Symposium on Antennas and Propagation, 2015Co-Authors: Bangda Zhou, Dan JiaoAbstract:In this paper, we develop a Linear-Complexity direct finite element solver to handle problems discretized into irregular meshes, and further to problems without mesh information. The new capabilities are validated by the simulation of an industry large-scale package structure with a highly irregular mesh and examples that have only matrices without mesh information. We also report simulation results of an IBM full package, where the resulting frequency-domain finite-element matrix of over 22.8488 million unknowns is directly factorized and solved in approximately 16 hours on a single core running at 3 GHz.
Wenwen Chai - One of the best experts on this subject based on the ideXlab platform.
-
Linear Complexity direct and iterative integral equation solvers accelerated by a new rank minimized cal h 2 representation for large scale 3 d interconnect extraction
IEEE Transactions on Microwave Theory and Techniques, 2013Co-Authors: Wenwen Chai, Dan JiaoAbstract:We develop a new rank-minimized H2-matrix-based representation of the dense system matrix arising from an integral-equation (IE)-based analysis of large-scale 3-D interconnects. Different from the H2-representation generated by the existing interpolation-based method, the new H2-representation minimizes the rank in nested cluster bases and all off-diagonal blocks at all tree levels based on accuracy. The construction algorithm of the new H2-representation is applicable to both real- and complex-valued dense matrices generated from scalar and/or vector-based IE formulations. It has a Linear Complexity, and hence, the computational overhead is small. The proposed new H2-representation can be employed to accelerate both iterative and direct solutions of the IE-based dense systems of equations. To demonstrate its effectiveness, we develop a Linear-Complexity preconditioned iterative solver as well as a Linear-Complexity direct solver for the capacitance extraction of arbitrarily shaped 3-D interconnects in multiple dielectrics. The proposed Linear-Complexity solvers are shown to outperform state-of-the-art H2-based Linear-Complexity solvers in both CPU time and memory consumption. A dense matrix resulting from the capacitance extraction of a 3-D interconnect having 3.71 million unknowns and 576 conductors is inverted in fast CPU time (1.6 h), modest memory consumption (4.4 GB), and with prescribed accuracy satisfied on a single core running at 3 GHz.
-
direct matrix solution of Linear Complexity for surface integral equation based impedance extraction of complicated 3 d structures
Proceedings of the IEEE, 2013Co-Authors: Wenwen Chai, Dan JiaoAbstract:We develop a Linear-Complexity direct matrix solution for the surface integral equation (IE)-based impedance extraction of arbitrarily shaped 3-D nonideal conductors embedded in a dielectric material. A direct inverse of a highly irregular system matrix composed of both dense and sparse matrix blocks is obtained in O(N) Complexity with N being the matrix size. It outperforms state-of-the-art impedance solvers, be they direct solvers or iterative solvers, with fast central processing unit (CPU) time, modest memory consumption, and without sacrificing accuracy, for both small and large number of unknowns. The inverse of a 2.68-million-unknown matrix arising from the extraction of a large-scale 3-D interconnect having 128 buses, which is a matrix solution for 2.68 million right-hand sides, was obtained in less than 1.5 GB memory and 1.3 h on a single CPU running at 3 GHz.
-
dense matrix inversion of Linear Complexity for integral equation based large scale 3 d capacitance extraction
IEEE Transactions on Microwave Theory and Techniques, 2011Co-Authors: Wenwen Chai, Dan JiaoAbstract:State-of-the-art integral-equation-based solvers rely on techniques that can perform a dense matrix-vector multiplication in Linear Complexity. We introduce the H2 matrix as a mathematical framework to enable a highly efficient computation of dense matrices. Under this mathematical framework, as yet, no Linear Complexity has been established for matrix inversion. In this work, we developed a matrix inverse of Linear Complexity to directly solve the dense system of Linear equations for the 3-D capacitance extraction involving arbitrary geometry and nonuniform materials. We theoretically proved the existence of the H2 matrix representation of the inverse of the dense system matrix, and revealed the relationship between the block cluster tree of the original matrix and that of its inverse. We analyzed the Complexity and the accuracy of the proposed inverse, and proved its Linear Complexity, as well as controlled accuracy. The proposed inverse-based direct solver has demonstrated clear advantages over state-of-the-art capacitance solvers such as FastCap and HiCap: with fast CPU time and modest memory consumption, and without sacrificing accuracy. It successfully inverts a dense matrix that involves more than one million unknowns associated with a large-scale on-chip 3-D interconnect embedded in inhomogeneous materials with fast CPU time and less than 5-GB memory.
-
an ℋ 2 based direct integral equation solver of Linear Complexity for full wave extraction of 3 d structures in multiple dielectrics
International Symposium on Antennas and Propagation, 2011Co-Authors: Wenwen Chai, Dan JiaoAbstract:A Linear Complexity direct matrix solution is developed for a full-wave-based impedance extraction of arbitrarily-shaped 3-D non-ideal conductors embedded in multiple dielectrics. It successfully overcomes the numerical challenge of directly solving a highly irregular system matrix that is mixed with both dense and sparse blocks. The proposed direct solver is shown to outperform state-of-the-art impedance solvers with fast CPU time, modest memory-consumption, and without sacrificing accuracy. The inverse of a 2.6-million-unknown matrix resulting from the impedance extraction of a large-scale 3-D interconnect having 128 buses, which is a matrix solution for 2.6 million right hand sides, was obtained in less than 1.5 GB memory and 1.3 hours on a single CPU running at 2.66 GHz.
-
direct matrix solution of Linear Complexity for surface integral equation based impedance extraction of high bandwidth interconnects
Design Automation Conference, 2011Co-Authors: Wenwen Chai, Dan JiaoAbstract:A Linear-Complexity direct matrix solution is developed for the surface-integral based impedance extraction of arbitrarily-shaped 3-D non-ideal conductors embedded in dielectric materials. It outperforms state-of-the-art impedance solvers with fast CPU-time, modest memory-consumption, and without sacrificing accuracy. The inverse of a 2.6-million-unknown matrix arising from the extraction of large-scale 3-D interconnects was obtained in 1.5 GB memory and 1.3 hours on a 3 GHz CPU.
Zhixiong Chen - One of the best experts on this subject based on the ideXlab platform.
-
Linear Complexity of legendre polynomial quotients
Iet Information Security, 2018Co-Authors: Zhixiong ChenAbstract:Let p be an odd prime and w <; p be a positive integer. The authors continue to investigate the binary sequence (f u ) over {0, 1} defined from polynomial quotients by (u w - u wp )/p modulo p. The (f u ) is generated in terms of (-1) f(u) which equals to the Legendre symbol of (u w - u wp )/p (mod p) for u ≥ 0. In an earlier work, the Linear Complexity of (f u ) was determined for w = p - 1 (i.e. the case of Fermat quotients) under the assumption of 2 p-1 /≡1( mod p 2 ). In this work, they develop a naive trick to calculate all possible values on the Linear Complexity of (f u ) for all 1 ≤ w <; p - 1 under the same assumption. They also state that the case of larger w( ≥ p) can be reduced to that of 0 ≤ w ≤ p - 1. So far, the Linear Complexity is almost determined for all kinds of Legendre-polynomial quotients.
-
Linear Complexity of legendre polynomial quotients
arXiv: Cryptography and Security, 2017Co-Authors: Zhixiong ChenAbstract:We continue to investigate binary sequence $(f_u)$ over $\{0,1\}$ defined by $(-1)^{f_u}=\left(\frac{(u^w-u^{wp})/p}{p}\right)$ for integers $u\ge 0$, where $\left(\frac{\cdot}{p}\right)$ is the Legendre symbol and we restrict $\left(\frac{0}{p}\right)=1$. In an earlier work, the Linear Complexity of $(f_u)$ was determined for $w=p-1$ under the assumption of $2^{p-1}\not\equiv 1 \pmod {p^2}$. In this work, we give possible values on the Linear Complexity of $(f_u)$ for all $1\le w
-
on the k error Linear Complexity of binary sequences derived from polynomial quotients
Science in China Series F: Information Sciences, 2015Co-Authors: Zhixiong Chen, Zhihua NiuAbstract:The k-error Linear Complexity is an important cryptographic measure of pseudorandom sequences in stream ciphers. In this paper, we investigate the k-error Linear Complexity of p2-periodic binary sequences defined from the polynomial quotients modulo p, which are the generalizations of the well-studied Fermat quotients. Indeed, first we determine exact values of the k-error Linear Complexity over the finite field \(\mathbb{F}_2\) for these binary sequences under the assumption of 2 being a primitive root modulo p2, and then we determine their k-error Linear Complexity over the finite field \(\mathbb{F}_p\). Theoretical results obtained indicate that such sequences possess ‘good’ error Linear Complexity.
-
on the k error Linear Complexity of binary sequences derived from polynomial quotients
arXiv: Cryptography and Security, 2013Co-Authors: Zhixiong Chen, Zhihua NiuAbstract:We investigate the $k$-error Linear Complexity of $p^2$-periodic binary sequences defined from the polynomial quotients (including the well-studied Fermat quotients), which is defined by $$ q_{p,w}(u)\equiv \frac{u^w-u^{wp}}{p} \bmod p ~ \mathrm{with} 0 \le q_{p,w}(u) \le p-1, ~u\ge 0, $$ where $p$ is an odd prime and $1\le w
-
trace representation and Linear Complexity of binary sequences derived from fermat quotients
arXiv: Number Theory, 2013Co-Authors: Zhixiong ChenAbstract:We describe the trace representations of two families of binary sequences derived from Fermat quotients modulo an odd prime $p$ (one is the binary threshold sequences, the other is the Legendre-Fermat quotient sequences) via determining the defining pairs of all binary characteristic sequences of cosets, which coincide with the sets of pre-images modulo $p^2$ of each fixed value of Fermat quotients. From the defining pairs, we can obtain an earlier result of Linear Complexity for the binary threshold sequences and a new result of Linear Complexity for the Legendre-Fermat quotient sequences under the assumption of $2^{p-1}\not\equiv 1 \bmod {p^2}$.
Zongduo Dai - One of the best experts on this subject based on the ideXlab platform.
-
trace representation and Linear Complexity of binary e th power residue sequences of period p
IEEE Transactions on Information Theory, 2011Co-Authors: Zongduo Dai, Guang Gong, Hongyeop SongAbstract:Let p = ef + 1 be an odd prime for some e and e and let f, be the finite field with Fp elements. In this paper, we explicitly describe the trace representations of the binary characteristic sequences (of period p) of all the cyclic difference sets D which are some union of cosets of eth powers He in Fp* (=Δ Fp\{0}) for e ≤ 12. For this, we define eth power residue sequences of period p, which include all the binary characteristic sequences mentioned above as special cases, and reduce the problem of determining their trace representations to that of determining the values of the generating polynomials of cosets of He in Fρ* at some primitive pth root of unity, and some properties of these values are investigated. Based on these properties, the trace representation and Linear Complexity not only of the characteristic sequences of all the known eth residue difference sets, but of all the sixth power residue sequences are determined. Furthermore, we have determined the Linear Complexity of a nonconstant eth power residue sequence for any e to be either p - 1 or p whenever (e, (p-1)/n) = 1, where n is the order of 2 mod p.
-
asymptotic behavior of normalized Linear Complexity of multi sequences
Lecture Notes in Computer Science, 2005Co-Authors: Zongduo Dai, Kyoki Imamura, Junhui YangAbstract:Asymptotic behavior of the normalized Linear Complexity L s (n) n of a multi-sequence s is studied in terms of its multidimensional continued fraction expansion, where L s (n) is the Linear Complexity of the length n prefix of s and defined to be the length of the shortest multi-tuple Linear feedback shift register which generates the length n prefix of s. A formula for limsup n→ ∞ L s (n)/n together with a lower bound, and a formula for lim inf n→ ∞ L s (n) n together with an upper bound are given. A necessary and sufficient condition for the existence of lim n→ ∞ L s (n) n is also given.
-
asymptotic behavior of normalized Linear Complexity of ultimately nonperiodic binary sequences
IEEE Transactions on Information Theory, 2004Co-Authors: Zongduo Dai, Kyoki Imamura, Shaoquan Jiang, Guang GongAbstract:For an ultimately nonperiodic binary sequence s={s/sub t/}/sub t/spl ges/0/, it is shown that the set of the accumulation values of the normalized Linear Complexity, L/sub s/(n)/n, is a closed interval centered at 1/2, where L/sub s/(n) is the Linear Complexity of the length n prefix s/sup n/=(s/sub 0/,s/sub 1/,...,s/sub n-1/) of the sequence s. It was known that the limit value of the normalized Linear Complexity is equal to 0 or 1/2 if it exists. A method is also given for constructing a sequence to have the closed interval [1/2-/spl Delta/, 1/2+/spl Delta/](0/spl les//spl Delta//spl les/1/2) as the set of the accumulation values of its normalized Linear Complexity.
-
asymptotic behavior of normalized Linear Complexity of ultimately non periodic binary sequences
International Symposium on Information Theory, 2004Co-Authors: Zongduo Dai, Shaoquan Jiang, K Imamura, Guang GongAbstract:This paper describes the asymptotic behavior of normalized Linear Complexity of ultimately nonperiodic binary sequence. The Linear Complexity of s/sup n/, L/sub s/(n), is defined as the length of the shortest Linear feedback shift register which generates s/sup n/. The research method and results studied in this paper seem to be very useful in characterizing the purely random sequence and distinguishing a key stream generator from a uniformly random sequence.
-
Linear Complexity for one symbol substitution of a periodic sequence over gf q
IEEE Transactions on Information Theory, 1998Co-Authors: Zongduo Dai, Kyoki ImamuraAbstract:It is shown that the Linear Complexity for one-symbol substitution of any periodic sequence over GF(q) can be computed without any condition on the minimal polynomial of the sequence.
Vladimir Edemskiy - One of the best experts on this subject based on the ideXlab platform.
-
about the k error Linear Complexity over mathbb f _p of sequences of length 2 p with optimal three level autocorrelation
arXiv: Cryptography and Security, 2018Co-Authors: Vladimir EdemskiyAbstract:We investigate the $k$-error Linear Complexity over $\mathbb{F}_p$ of binary sequences of length $2p$ with optimal three-level autocorrelation. These balanced sequences are constructed by cyclotomic classes of order four using a method presented by Ding et al.
-
the Linear Complexity of binary sequences of length 2p with optimal three level autocorrelation
Information Processing Letters, 2016Co-Authors: Vladimir Edemskiy, A PalvinskiyAbstract:In this paper we derive the Linear Complexity of binary sequences of length 2p with optimal three-level autocorrelation. These almost balanced and balanced sequences are constructed by cyclotomic classes of order four using a method presented by Ding et al. We investigate the Linear Complexity of above-mentioned sequences over the finite fields of different orders. We derive the Linear Complexity of binary sequences of length 2p with optimal three-level autocorrelation.These sequences are constructed by cyclotomic classes of order four.We show the Linear Complexity of these sequences to be high over the finite fields of odd order.
-
Linear Complexity of quaternary sequences of length pq with low autocorrelation
Journal of Computational and Applied Mathematics, 2014Co-Authors: Vladimir Edemskiy, Andrey IvanovAbstract:We derive the Linear Complexity of quaternary sequences of length pq with low autocorrelation over the finite field of four elements and over the finite ring of order 4. Also we examine the Linear Complexity of the other sequences of length pq.
-
autocorrelation and Linear Complexity of quaternary sequences of period 2p based on cyclotomic classes of order four
International Symposium on Information Theory, 2013Co-Authors: Vladimir Edemskiy, Andrew IvanovAbstract:We examine the Linear Complexity and the autocorrelation of new quaternary cyclotomic sequences of period 2p. The sequences are constructed via the cyclotomic classes of order four.
-
autocorrelation and Linear Complexity of quaternary sequences of period 2p based on cyclotomic classes of order four
arXiv: Information Theory, 2013Co-Authors: Vladimir Edemskiy, Andrew IvanovAbstract:We examine the Linear Complexity and the autocorrelation properties of new quaternary cyclotomic sequences of period 2p. The sequences are constructed via the cyclotomic classes of order four.
