A Fast DVM Algorithm for Wideband Time-Delay Multi-Beam Beamformers
Abstract
This paper presents a sparse factorization for the delay Vandermonde matrix (DVM) along with fast, exact, radix-2, and recursive algorithms to compute the DVM-vector product for wideband multi-beam antenna arrays. The proposed algorithms enable low-complexity wideband beamformers in emerging millimeter-wave wireless communication networks by reducing the complexity of$N$-beam wideband beamforming from$\mathcal {O}(N^{2})$to$\mathcal {O}(N \mathrm{\: log\:} N)$, where$N=2^{r}(r \geq 1)$. As a result, the algorithms are faster than the brute-force computation of the DVM-vector product and more efficient than the direct realization of true-time-delay-based multi-beam beamformers. The proposed low-complexity algorithms' signal flow graph (SFG) is also presented to highlight their suitability for hardware implementations. The 2-D frequency responses of DVM-based beamformers are explained through an array signal processing example. Simulation results suggest that integrated circuit (IC) implementations of the SFG significantly reduce chip area and power consumption.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The parallel realization of N beams using a network of TTDs with durations set to integer multiples of τ0 leads to an N-beam TTD multi-beam beamformer with an underlying mathematical framework given by the DVM.
“The parallel realization of N beams using a network of TTDs with durations set to integer multiples of τ0 leads to an N-beam TTD multi-beam beamformer with an underlying mathematical framework given by the DVM [7,8,9,10,11].”
From Thiran Filters for Wideband DSP-Based Multi-Beam True Time Delay RF Sensing Applications (2024) · cites this paper as [11]
The paper proposes a low-complexity wideband TTD digital DVM algorithm using Thiran fractional delays.
“Thus, with this and from the prior work on DVM [7,8,9,10,11], we propose a low-complexity wideband TTD digital DVM algorithm using Thiran fractional delays.”
From Thiran Filters for Wideband DSP-Based Multi-Beam True Time Delay RF Sensing Applications (2024) · cites this paper as [11]
The DVM algorithm in [11] shows significant efficiency, surpassing 90%, for DVM sizes of N≥256.
“However, the DVM algorithm in [11] shows significant efficiency, surpassing 90%, for DVM sizes of N≥256.”
From Thiran Filters for Wideband DSP-Based Multi-Beam True Time Delay RF Sensing Applications (2024) · cites this paper as [11]
The authors proposed an O(NlogN) DVM algorithm having sparse factors to achieve multi-directional TTD wideband beamforming to solve the longstanding beam squint problem in [11].
“To overcome the above challenge, we proposed an O(NlogN) DVM algorithm having sparse factors to achieve multi-directional TTD wideband beamforming to solve the longstanding beam squint problem in [11].”
From Thiran Filters for Wideband DSP-Based Multi-Beam True Time Delay RF Sensing Applications (2024) · cites this paper as [11]
The ddvm algorithm exhibits a higher count of adders and gain-delay blocks compared to the algorithms presented in [10,11].
“The ddvm algorithm exhibits a higher count of adders and gain–delay blocks compared to the algorithms presented in [10,11].”
From Thiran Filters for Wideband DSP-Based Multi-Beam True Time Delay RF Sensing Applications (2024) · cites this paper as [11]
The factor e−jωτ associated with analog DVM beamforming can be efficiently approximated on chip by CMOS APFs.
“The factor e−jωτ is associated with the factorization of the AN and can be efficiently approximated on chip by CMOS APFs [7,8,9,10,11,48,49].”
From Thiran Filters for Wideband DSP-Based Multi-Beam True Time Delay RF Sensing Applications (2024) · cites this paper as [11]
Despite the algorithms presented in [11] exhibiting a complexity of O(NlogN), this algorithm does not yield favorable outcomes when applied to antenna arrays with a small number of elements, specifically 4 and 8.
“Despite the fact that the algorithms presented in [11] exhibit a complexity of O(NlogN), this algorithm does not yield favorable outcomes when applied to antenna arrays with a small number of elements, specifically 4 and 8.”
From Thiran Filters for Wideband DSP-Based Multi-Beam True Time Delay RF Sensing Applications (2024) · cites this paper as [11]
The algorithms in [10,11] have adders and gain-delay block counts of the order O(NlogN), whereas the ddvm algorithm maintains these counts of less than O(N^2).
“This is because the algorithms in those papers have adders and gain–delay block counts of the order O(NlogN), whereas the ddvm algorithm maintains these counts of less than O(N2).”
From Thiran Filters for Wideband DSP-Based Multi-Beam True Time Delay RF Sensing Applications (2024) · cites this paper as [11]
Cites
An algorithm for the machine calculation of complex Fourier series
Cooley, J. W., & Tukey, J. W. (1965) · Mathematics of Computation · doi:10.1090/s0025-5718-1965-0178586-1 · Cited by 13,154 · see citing works
Trees, H. L. V. (2002) · Wiley eBooks · doi:10.1002/0471221104 · Cited by 5,187 · see citing works
Wang, Y., Li, J., & Stoica, P. (2005) · Synthesis lectures on signal processing · doi:10.1007/978-3-031-02525-9 · Cited by 2,887 · see citing works
Rappaport, T. S., Xing, Y., Kanhere, O., Ju, S., Madanayake, A., Mandal, S., Alkhateeb, A., & Trichopoulos, G. C. (2019) · IEEE Access · doi:10.1109/access.2019.2921522 · Cited by 2,617 · cited 1× · see citing works
“Wideband transceivers for emerging 5G/6G wireless networks use large-scale arrays to provide high antenna gain, thus compensating for high path loss [32].”
BackgroundSelf-citationEnz, C., & Temes, G. C. (1996) · Proceedings of the IEEE · doi:10.1109/5.542410 · Cited by 1,878 · see citing works
Computational Frameworks for the Fast Fourier Transform
Loan, C. F. V. (1992) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611970999 · Cited by 1,292 · see citing works
Wide-angle microwave lens for line source applications
Rotman, W., & Turner, R. (1963) · IRE Transactions on Antennas and Propagation · doi:10.1109/tap.1963.1138114 · Cited by 841 · see citing works
Introduction to Applied Mathematics
Strang, G., & Freund, L. B. (1986) · Journal of Applied Mechanics · doi:10.1115/1.3171799 · Cited by 664 · see citing works
Analog Versus Digital: Extrapolating from Electronics to Neurobiology
Sarpeshkar, R. (1998) · Neural Computation · doi:10.1162/089976698300017052 · Cited by 496 · see citing works
Solution of Vandermonde systems of equations
Björck, Ȧ., & Pereyra, V. (1970) · Mathematics of Computation · doi:10.1090/s0025-5718-1970-0290541-1 · Cited by 398 · see citing works
A modified split-radix fft with fewer arithmetic operations
Johnson, S. G., & Frigo, M. (2007) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2006.882087 · Cited by 380 · see citing works
Fast Fourier Transform - Algorithms and Applications
Rao, K. R., Kim, D. N., & Hwang, J.-J. (2010) · Signals and Communication Technology · doi:10.1007/978-1-4020-6629-0 · Cited by 378 · see citing works
Fast Algorithms for Signal Processing
Blahut, R. E. (2010) · doi:10.1017/cbo9780511760921 · Cited by 274 · see citing works
Fast Reliable Algorithms for Matrices with Structure
Kailath, T., & Sayed, A. H. (1999) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611971354 · Cited by 253 · see citing works
Structured Matrices and Polynomials
Pan, V. Y. (2001) · doi:10.1007/978-1-4612-0129-8 · Cited by 203 · see citing works
The Accurate and Efficient Solution of a Totally Positive Generalized Vandermonde Linear System
Demmel, J., & Koev, P. (2005) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/s0895479804440335 · Cited by 154 · see citing works
Complexity of multiplication with vectors for structured matrices
Gohberg, I., & Olshevsky, V. (1994) · Linear Algebra and its Applications · doi:10.1016/0024-3795(94)90189-9 · Cited by 127 · see citing works
An economical method for calculating the discrete Fourier transform
Yavne, R. (1968) · AFIPS Fall Joint Computer Conference (FJCC) · doi:10.1145/1476589.1476610 · Cited by 113 · see citing works
Fast algorithms with preprocessing for matrix-vector multiplication problems
Gohberg, I., & Olshevsky, V. (1994) · Journal of Complexity · doi:10.1006/jcom.1994.1021 · Cited by 90 · see citing works
RF Analog Beamforming Fan Filters Using CMOS All-Pass Time Delay Approximations
Wijenayake, C. A., Xu, Y., Madanayake, A., Belostotski, L., & Bruton, L. T. (2012) · IEEE Transactions on Circuits and Systems I Regular Papers · doi:10.1109/tcsi.2012.2185294 · Cited by 74 · see citing works
Self-citationA New Second-Order All-Pass Filter in 130-nm CMOS
Ahmadi, P., Maundy, B., Elwakil, A. S., Belostotski, L., & Madanayake, A. (2016) · IEEE Transactions on Circuits and Systems II: Express Briefs · doi:10.1109/tcsii.2015.2482578 · Cited by 59 · see citing works
Self-citationExplicit factorization of the Vandermonde matrix
Oruç, H., & Phillips, G. M. (2000) · Linear Algebra and its Applications · doi:10.1016/s0024-3795(00)00124-5 · Cited by 57 · see citing works
Reichel, L., & Opfer, G. (1991) · Mathematics of Computation · doi:10.1090/s0025-5718-1991-1094957-9 · Cited by 55 · see citing works
Accurate computations with Said–Ball–Vandermonde matrices
Marco, A., & Martínez, J. (2010) · Linear Algebra and its Applications · doi:10.1016/j.laa.2009.12.034 · Cited by 51 · see citing works
Displacement structure approach to polynomial Vandermonde and related matrices
Kailath, T., & Olshevsky, V. (1997) · Linear Algebra and its Applications · doi:10.1016/s0024-3795(96)00315-1 · Cited by 50 · see citing works
Perera, S. M., Ariyarathna, V., Udayanga, N., Madanayake, A., Wu, G., Belostotski, L., Wang, Y., Mandal, S., Cintra, R. J., & Rappaport, T. S. (2018) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2018.2822940 · Cited by 50 · see citing works
Self-citationAccurate SVDs of polynomial Vandermonde matrices involving orthonormal polynomials
Demmel, J. W., & Koev, P. (2005) · Linear Algebra and its Applications · doi:10.1016/j.laa.2005.09.014 · Cited by 42 · see citing works
On the LU factorization of the Vandermonde matrix
Yang, S.-L. (2005) · Discrete Applied Mathematics · doi:10.1016/j.dam.2004.08.003 · Cited by 37 · see citing works
Inverses of Vandermonde matrices
Parker, F. D. (1964) · The American Mathematical Monthly · doi:10.2307/2313246 · Cited by 35 · cited 1× · see citing works
“…problems, such as computing the inverse of a Vandermonde matrix (resulting in inversion formulas or inversion algorithms) or solving systems of equations with a Vandermonde matrix as the coefficient matrix [42], [43], [44], [45], [46], [47], [48], [49], [50], [51], are not considered in this paper.”
True-Time-Delay Beamforming Receiver With RF Re-Sampling
Spoof, K., Unnikrishnan, V., Zahra, M., Stadius, K., Kosunen, M., & Ryynänen, J. (2020) · IEEE Transactions on Circuits and Systems I Regular Papers · doi:10.1109/tcsi.2020.3005475 · Cited by 34 · see citing works
Algorithms for FFT Beamforming Radio Interferometers
Masui, K. W., Shaw, J. R., Ng, C., Smith, K. M., Vanderlinde, K., & Paradise, A. (2019) · The Astrophysical Journal · doi:10.3847/1538-4357/ab229e · Cited by 33 · see citing works
Ariyarathna, V., Madanayake, A., Tang, X., Coelho, D. F. G., Cintra, R. J., Belostotski, L., Mandal, S., & Rappaport, T. S. (2018) · IEEE Journal on Emerging and Selected Topics in Circuits and Systems · doi:10.1109/jetcas.2018.2832177 · Cited by 32 · see citing works
Self-citationAll-Pass Filter-Based 2-D IIR Filter-Enhanced Beamformers for AESA Receivers
Wijenayake, C. A., Madanayake, A., Belostotski, L., Xu, Y., & Bruton, L. T. (2014) · IEEE Transactions on Circuits and Systems I Regular Papers · doi:10.1109/tcsi.2014.2309833 · Cited by 27 · see citing works
Self-citationVandermonde factorization of Toeplitz matrices and applications in filtering and warping
Backstrom, T. (2013) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2013.2282271 · Cited by 26 · see citing works
Symmetric functions and the Vandermonde matrix
Oruç, H., & Akmaz, H. K. (2004) · Journal of Computational and Applied Mathematics · doi:10.1016/j.cam.2004.01.032 · Cited by 25 · see citing works
Adaptive Beamforming Applied to a Cylindrical Sonar Array Using an Interpolated Array Transformation
Blomberg, A. E. A., Austeng, A., & Hansen, R. E. (2011) · IEEE Journal of Oceanic Engineering · doi:10.1109/joe.2011.2169611 · Cited by 24 · see citing works
Fast approximate computations with Cauchy matrices and polynomials
Pan, V. (2017) · Mathematics of Computation · doi:10.1090/mcom/3204 · Cited by 21 · cited 1× · see citing works
“The DVM factorizations in [5], [10] do not utilize either quasiseparability and displacement equations as in [14], [15], [16], or a O ( N 3 ) algorithm to compute the SVD of polynomial Vandermonde matrices as in [17].”
MethodA Steerable DC-1 GHz all-pass filter-Sum RF space-time 2-D beam filter in 65 nm CMOS
Wijenayake, C., Madanayake, A., Xu, Y., Belostotski, L., & Bruton, L. T. (2013) · 2013 IEEE International Symposium on Circuits and Systems (ISCAS2013) · doi:10.1109/iscas.2013.6572086 · Cited by 19 · see citing works
Self-citationPerera, S. M., Madanayake, A., & Cintra, R. J. (2020) · IEEE Access · doi:10.1109/access.2020.2970342 · Cited by 18 · see citing works
Self-citationA fast method to diagonalize a Hankel matrix
Boley, D. L., Luk, F. T., & Vandevoorde, D. (1998) · Linear Algebra and its Applications · doi:10.1016/s0024-3795(98)10101-5 · Cited by 17 · cited 2× · see citing works
“However, the factorization proposed in [38], [39], [40], [41] requires O(N2) operations to decompose Toeplitz and Hankel matrices via Vandermonde matrices.”
MethodBella, T., Eidelman, Y., Gohberg, I., Koltracht, I., & Olshevsky, V. (2007) · Linear Algebra and its Applications · doi:10.1016/j.laa.2006.08.032 · Cited by 17 · see citing works
Multi-beam 4 GHz microwave apertures using current-mode DFT approximation on 65 nm CMOS
Ariyarathna, V., Kulasekera, S., Madanayake, A., Lee, K., Suarez, D., Cintra, R. J., Bayer, F. M., & Belostotski, L. (2015) · IEEE MTT-S International Microwave Symposium digest · doi:10.1109/mwsym.2015.7167112 · Cited by 16 · see citing works
Self-citationEfficient and Self-Recursive Delay Vandermonde Algorithm for Multi-beam Antenna Arrays
Perera, S. M., Madanayake, A., & Cintra, R. J. (2020) · IEEE Open Journal of Signal Processing · doi:10.1109/ojsp.2020.2991586 · Cited by 15 · see citing works
Self-citationA fast bjorck-pereyra-type algorithm for solving hessenberg-quasiseparable-vandermonde systems
Bella, T., Eidelman, Y., Gohberg, I., Koltracht, I., & Olshevsky, V. (2009) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/060676635 · Cited by 14 · see citing works
Design methodology of an analog 9-beam squint-free wideband IF multi-beamformer for mmW applications
Ariyarathna, V., Udayanga, N., Madanayake, A., Perera, S. M., Belostotski, L., & Cintra, R. J. (2017) · 2017 Moratuwa Engineering Research Conference (MERCon) · doi:10.1109/mercon.2017.7980488 · Cited by 11 · see citing works
Self-citationPerformance evaluation of pre- and post-FFT beamforming methods in pilot-assisted SIMO-OFDM systems
Seydnejad, S. R., & Akhzari, S. (2015) · Telecommunication Systems · doi:10.1007/s11235-015-0007-8 · Cited by 5 · see citing works
Implementation And Evaluation Of The Vandermonde Transform
Bäckström, T., Boley, D. L., & Fischer, J. (2014) · Zenodo (CERN European Organization for Nuclear Research) · doi:10.5281/zenodo.43749 · Cited by 5 · see citing works
Matrix Structures in Queuing Models
Bini, D. A. (2016) · Lecture notes in mathematics · doi:10.1007/978-3-319-49887-4_2 · Cited by 5 · see citing works
A Fast Algorithm to Solve Delay Vandermonde Systems in Phased-Array Digital Receivers
Perera, S. M., Madanayake, A., Ogle, A., Silverio, D., & Huang, J. Q. (2021) · IEEE Transactions on Aerospace and Electronic Systems · doi:10.1109/taes.2021.3086356 · Cited by 5 · see citing works
Self-citationAn Offset-Canceling Approximate-DFT Beamforming Architecture for Wireless Transceivers
Zhao, H., Mandal, S., Ariyarathna, V., Madanayake, A., & Cintra, R. J. (2018) · IEEE International Symposium on Circuits and Systems proceedings · doi:10.1109/iscas.2018.8351765 · Cited by 4 · see citing works
Self-citationQuasiseparable Approach to Matrices of Vandermonde Type
Perera, S. M. (2012) · Cited by 4 · see citing works
Self-citation
Flagged first, then by citations
Cited by
Sorted by citations
Multi-Beam Beamforming-Based ML Algorithm to Optimize the Routing of Drone Swarms
Myers, R. J., Perera, S. M., McLewee, G., Huang, D., & Song, H. H. (2024) · Drones · doi:10.3390/drones8020057 · Cited by 7 · see citing works
Self-citationThiran Filters for Wideband DSP-Based Multi-Beam True Time Delay RF Sensing Applications
Perera, S. M., Rathnasekara, G., & Madanayake, A. (2024) · Sensors · doi:10.3390/s24020576 · Cited by 5 · see citing works
“In [11], the “multiplication counts” in the frequency domain—albeit in the analog domain—are a combined result of analog gains (amplifiers) and time delays in the SFG when realized in a time-domain circuit.”
BackgroundMethodResultInfluentialSelf-citationA Low-Complexity LSTM Network to Realize Multibeam Beamforming
Aluvihare, H., Shanahan, C., Perera, S. M., Sivasankar, S., Kumarasiri, U., Madanayake, A., & Li, X. (2024) · IEEE International Conference on Wireless for Space and Extreme Environments (WiSEE) · doi:10.1109/wisee61249.2024.10850415 · Cited by 4 · see citing works
Self-citationPerera, S. M., Lingsch, L., Madanayake, A., & Belostotski, L. (2025) · Journal of Computational and Applied Mathematics · doi:10.1016/j.cam.2025.117152 · Cited by 3 · see citing works
Self-citationA Demonstration of a Wideband Low-Complexity Multibeam Analog Beamforming Network
Xie, H., Madanayake, A., Perera, S. M., Okoniewski, M., & Belostotski, L. (2025) · IEEE Transactions on Microwave Theory and Techniques · doi:10.1109/tmtt.2025.3543480 · Cited by 3 · see citing works
Self-citationA low-complexity algorithm to search for Legendre pairs
Perera, S. M., & Kotsireas, I. (2025) · Linear Algebra and its Applications · doi:10.1016/j.laa.2025.01.010 · Cited by 2 · see citing works
Self-citationAluvihare, H., Sivasankar, S., Li, X., Madanayake, A., & Perera, S. M. (2025) · IEEE Journal of Radio Frequency Identification · doi:10.1109/jrfid.2025.3602901 · Cited by 2 · see citing works
Self-citationPerera, S. M., & Madanayake, A. (2024) · IEEE International Conference on RFID Technology and Applications (RFID-TA) · doi:10.1109/rfid-ta64374.2024.10965176
Self-citationA Fast True Time-Delay Wideband Multi-Beam Beamforming Algorithm Based on a 16-Beam Approximate-DVM
Perera, S. M., Lingsch, L., Tuztas, A., & Madanayake, A. (2025) · IEEE Access · doi:10.1109/access.2025.3573930
Self-citationA low-complexity structured neural network to realize states of dynamical systems
Aluvihare, H., Lingsch, L., Li, X., & Perera, S. M. (2026) · Linear Algebra and its Applications · doi:10.1016/j.laa.2026.08.036
Self-citationReal-Time Non-Uniform Fast Fourier Transform for Multibeam Digital Beamforming
Angeletti, P., Coskun, A., & Kale, İ. (2026) · IEEE Open Journal of Signal Processing · doi:10.1109/ojsp.2026.3719966
- Authors
- Perera, S. M., Lingsch, L., Madanayake, A., Mandal, S., & Mastronardi, N.
- Affiliations
- Embry-Riddle Aeronautical University Daytona Beach Florida Campus (US)
- Florida International University (US)
- University of Florida (US)
- Istituto per le Applicazioni del Calcolo Mauro Picone (IT)
- Venue
- IEEE Transactions on Signal Processing
- Published
- 2022
- Volume
- 70
- Pages
- 5913-5925
- ISSN
- 1053-587X (ISSN-L)
- 1941-0476
- OpenAlex
- W4312875715
- Cited by
- 11
- References
- 51
- Citations by year
- 2026: 2 · 2025: 5 · 2024: 4
- FWCI
- 1.04
- Type
- journal article
- Language
- en
- Open access
- closed
- Licence
- Locations
- IEEE Transactions on Signal Processing (publishedVersion)
- Funders
- National Science Foundation (1902283)
- Topics
- Physical Sciences › Computer Science › Signal Processing › Digital Filter Design and Implementation
- Physical Sciences › Computer Science › Signal Processing › Direction-of-Arrival Estimation Techniques
- Physical Sciences › Engineering › Electrical and Electronic Engineering › Millimeter-Wave Propagation and Modeling
- Keywords
- wideband beamforming, sparse factorization, radix-2 algorithm, recursive algorithm, low-complexity algorithms, millimeter-wave communication, true-time delay, signal flow graph, hardware implementation, integrated circuit design, antenna arrays
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
