# A Dual Threshold Analogue Content Addressable Memory

Patrick Foster∗, Alex Serb∗, and Themis Prodromakis∗
Email: {pfoster4, aserb<EMAIL_ADDRESS>
∗Centre for Electronics Frontiers, University of Edinburgh

###### Abstract

Advances in machine learning and neuromorphic systems are fuelled by the
development of architectures required for these applications, such as content
addressable memory. In an attempt to address this need, this paper presents a
new RRAM tuned window comparator, building upon existing work in
reconfigurable computing. The circuit uses a low component count at 6T2R2M,
comparable with the most compact existing cells of this type. This paper will
present this design, demonstrating its operation with TiOx memristive devices,
showing its controllability and specificity. This paper will then simulate the
energy dissipated in its operation, showing it to be below
$100\text{\,}\mathrm{pJ}$ per test, comparable to existing works.

###### Index Terms:

Associative memory, content addressable memory, RRAM, memristor

##  I Introduction

Content addressable memory (CAM) is a broad term describing memory
technologies where the memory cells compare their stored state with an input
locally. This allows a bank of CAM to be quickly searched by applying the
information that is being sought to the input of the array and monitoring the
cell outputs. The combining of low level computing tasks with memory blurs the
boundary between the two and could allow for advances in conventional
computing[1], but has further potential in machine learning applications. CAM
can serve as the foundation of the design of artificial neural nets and other
neuromorphic systems[2].

Figure 1: A diagram of an example analogue CAM array.

Content addressable memory technologies can be divided into two types: binary
CAM and analogue CAM. Binary CAM stores only a high or low value, and usually
compare this stored value with a binary input[3]. CMOS SRAM based CAM cells
commonly find use in network switches, where they are used to store easily
searchable tables of MAC address for faster signal routing[4]. In some cases,
CAM can have a third stored state for ’don’t care’; this is called ternary
CAM[5][6]. While CMOS binary CAM is well established, there is ongoing
research in the area, trying to integrate novel nonvolatile memory elements
such as RRAM[7]. Analogue CAM can have a range of different implementations,
but often takes the form of a window comparator. In addition to their use in
neuromorphic systems[8], this type of CAM can also be used in analogue signal
analysis methods such as template matching[9]. Unlike binary CAM research,
where the goal is to add nonvolatility to the cells without increasing power
dissipation, analogue CAM research seeks to replace high power dissipation and
area comparators with simplified circuits that take advantage of the analogue
nature of emerging memory technologies. While there are more attempts to use
FeRAM[10][11][12] for this purpose, an alternative memory for this application
is RRAM[13][14], due to the granularity of states in RRAM technologies and the
ease of controlling circuits with resistive elements. This works seeks to
build upon existing work in reconfigurable computing[15], with the aim of
producing a circuit closer in operation to the work of Can Li et al.[16]. This
paper will demonstrate the validity of resistive models of the circuit under
consideration, and then assess an integrated implementation of the design for
the purpose of proving the concept and comparison with existing work.

##  II Circuit Design

Figure 2: A diagram of the split TXL circuit.

The circuit considered (Fig. 2) is based upon a skewed inverter design. Two
complementary FET pairs with source degeneration are used as the input stage
with their outputs assessed by an XOR mode transmission gate. The ratio
between source degeneration on the input PMOS and NMOS alters the threshold of
the inverter. As the threshold is dependent on the ratio between the top and
bottom degeneration resistors and not the total resistance of the branch, the
threshold can be controlled by altering the state of only one of them. As
such, this design uses a single dynamic RRAM device to control each threshold,
with the opposing degeneration being provided by a static balancing resistor.
When the input is above the threshold of the M1 branch inverter and below the
threshold of the M2 branch inverter, both the PMOS and NMOS of the output
stage pass current, producing an output signal. While this configuration
permits the independent control of each threshold with a single resistive
device, the dynamic range required is quite high, although not to the degree
required by previous works[16]. This is because the dynamic element must go
both above and below the balancing resistor by a factor of 10 to achieve a
reasonable range of threshold values. As there are DC paths in this design,
the energy per test may not be as low as designs with adiabatic operation, but
the small footprint should be outstanding.

##  III Measurement

Existing models of memristive devices are limited in scope and detail, so
simulations of this CAM circuit are somewhat difficult. Analysis of this
circuit must therefore be done with a physical model. In theory, the state of
the memristors used should only matter at two points: the current at which the
inverter switches, and at zero current. Because of this, models of CAM cell
using linear resistors should be a reasonable approximation of the intended
circuit, but this assumption must be tested. To this end, two CAM array PCBs
were designed for use with an existing instrument platform[17]. The PCB
implementations of this circuit use the SSM6L36TU,LF[18], along with
$1\text{\,}\mathrm{M\SIUnitSymbolOhm}$ balancing and output resistors. The
FETs used are small signal MOSFETs with threshold voltages comparable to
integrated FETs. The high value balancing resistor result in low supply
current in the skewed inverters, allowing the inverters to switch a little
closer to the supplies, reducing the required headroom. For the dynamic
element, the resistor model (Fig. 4) used a multiplexer switched array of 16
resistors, geometrically spaced between
$100\text{\,}\mathrm{k\SIUnitSymbolOhm}$ and
$10\text{\,}\mathrm{M\SIUnitSymbolOhm}$. The memristor model (Fig. 6) used a
PLCC68 package of $30\times$30\text{\,}\mathrm{\SIUnitSymbolMicro m}$$
monolayer titanium oxide memristors.

Figure 3: A diagram of the method used to determine window width. In this case
the window width is calculated as $1.1\text{\,}\mathrm{V}$.

To assess how the window responded to changes in the control devices, the
current output is denoised with a 50 sample moving average filter and the
differential calculated. The window width is calculated as the difference in
input voltage between the minimum and maximum of the derivative (Fig. 3). This
method was chosen as it provides a meaningful result in circumstances where
the window peak is not constant, where a more common method such as full width
at half maximum (FWHM) might not. The differential method typically gives a
slightly more pessimistic valuation of the circuit performance than FWHM.

###  III-A Resistor Array Model

Figure 4: A photograph of the resistor version of the PCB model of the CAM
cell.

The behaviour of the resistor model was measured by setting one of the dynamic
elements to its maximum value and conducting an input sweep at each step of
the other dynamic element. In this model, the CAM circuit was supplied at
$1.8\text{\,}\mathrm{V}$ and the input swept from $0\text{\,}\mathrm{V}$ to
the supply voltage. The current was measured at every DAC increment, for a
total of 5898 samples.

(a)

(b)

(c)

(d)

Figure 5: a) A graph of the IV characteristics of the PCB model of the CAM
circuit, sweeping M1 between $10\text{\,}\mathrm{M\SIUnitSymbolOhm}$ and
$100\text{\,}\mathrm{k\SIUnitSymbolOhm}$. b) A graph of an identical sweep of
M2. c) A graph of the width of the window as a function of resistor state. d)
A graph of the maximum window width as a function of the supply voltage.

As can be seen in 5, the circuit operates in the intended manner, producing a
significant output current at input values between the two thresholds. The
upper threshold was measured to be almost linear with the logarithm of the
control resistor. The upper threshold displayed the ramp-step-ramp of a
current starved inverter. This is because the NMOS in the output branch acts
as a voltage follower. This somewhat compromises the specificity of the
circuit. The lower threshold displayed significant nonlinearity of control,
with a pronounced s-curve. Additionally, the maximum window width was
calculated for a range of supply voltages. This was found to be linear,
implying that the headroom required is a function of the threshold value of
the MOSFETs used, regardless of the operating current.

###  III-B Memristor Model

Figure 6: A photograph of the memristor version of the PCB model of the CAM
cell.

For the memristor tests, the devices were set to a new state with
$100-$500\text{\,}\mathrm{\SIUnitSymbolMicro s}$$ pulses and then read at
$250\text{\,}\mathrm{mV}$, before performing a sweep of the input voltage in
$1\text{\,}\mathrm{mV}$ steps, reading the current at each step for a total of
1801 samples per trace. For the purposes of calculating the threshold
position, the current output curve was denoised with the same 50 sample moving
average filter. In this case, the same 50 samples represents a larger portion
of the trace, but this was required as some of the tests produced
exceptionally noisy results. The memristor version of this experiment proved
much more challenging to run. The monolayer titanium oxide memristors used in
this test are an early memristor technology and come with many of the expected
teething issues, presenting difficulty setting new resistive states and
holding existing ones. During writing, the state of the devices would relax
back towards the previous state and in some tests, the state of the control
device would fluctuate. In the sweep of M1, some tests saw the memristor
taking random values within a small range, as can be seen in the top right of
figure 7. In the sweep of M2, a test at high resistive state saw the control
device switching between two distinct values, as can be seen in the outermost
trace of the top left of figure 7. This may be indicative of the formation
(and disruption) of conductive filaments within the titanium oxide layer, as
this is one of the hypothesised mechanisms of the memristive behaviour of
these devices[19]. Attempts were made to run tests using bilayer titanium
oxide memristors, but the devices used could not be reliably set to resistive
states above $500\text{\,}\mathrm{k\SIUnitSymbolOhm}$, which rendered them
useless for the bias conditions of this model.

Figure 7: a) A graph of the IV characteristics of the memristor model,
sweeping M1 from $8\text{\,}\mathrm{M\SIUnitSymbolOhm}$ to
$30\text{\,}\mathrm{k\SIUnitSymbolOhm}$, with M2 at
$6$-$8\text{\,}\mathrm{M\SIUnitSymbolOhm}$. b) A graph of a similar sweep of
M2 from $200\text{\,}\mathrm{k\SIUnitSymbolOhm}$ to
$8.6\text{\,}\mathrm{M\SIUnitSymbolOhm}$, with M1 at
$5.6$-$6.5\text{\,}\mathrm{M\SIUnitSymbolOhm}$. c) A scatter plot of the
window width as a function of the memristor state. Note that the X axis is
reversed compared to the bottom right figure. d) A scatter plot of the window
width as a function of memristor state.

Due to the difficulties holding a device at a specific state, instead of
assessing the window width, the position of each threshold was calculated.
While this is less useful in characterising the circuit, it prevents issues
with setting one threshold from affecting the assessment of the other. Despite
this, the tests on the bottom threshold showed a similar s-curve shape to the
resistor model. The shape of the window produced is also very similar to the
shape obtained in the resistor model. The upper threshold was not so well
behaved, showing significant loss in the sharpness of the transition. Further,
there was a loss of monotonicity at high resistive states, although this may
be due to changes in the state of the M2 device between the measurement taken
at the start of each test and the state it held during the test. Despite the
irregularities, the traces produce in the tests of the memristor model are
clearly of comparable shape and range of position to the results of the
resistor model. From this, it can be concluded that resistor models of the
circuit can be assumed a reasonable model of the circuit for the assessment of
characteristics not explicitly related to the threshold shape, such as power
consumption and footprint area.

##  IV Integrated Simulation

###  IV-A Design

To estimate the power consumed by the circuit, an integrated circuit model of
the design was produced in Cadence Virtuoso using the TSMC180BCD product
development kit. This technology node uses planar MOSFETs, for either
$1.8\text{\,}\mathrm{V}$ or $5\text{\,}\mathrm{V}$. As integrated design
provides much greater control of the specifics of the transistors used, three
versions of the circuit were designed, with different sizes for the transistor
used in the two inverters (Fig. I): one with minimum size input transistors,
one with wide input transistors, and one with minimum size native NMOS and
conventional PMOS input transistors. In all cases the two transistors on the
output branch were minimum size. All transistors are $1.8\text{\,}\mathrm{V}$
devices. While it may be possible to replace the balancing resistors with
static memristors, the assumption is that polysilicon resistors will be used.
This constraint makes the $1\text{\,}\mathrm{M\SIUnitSymbolOhm}$ balancing
resistors of the PCB model wildly impractical, due to the area required. The
simulations shown here were conducted with
$10\text{\,}\mathrm{k\SIUnitSymbolOhm}$ balancing resistors and dynamic
resistors of $1\text{\,}\mathrm{k\SIUnitSymbolOhm}$ to
$100\text{\,}\mathrm{k\SIUnitSymbolOhm}$. While this strips the circuit of a
significant portion of its range, it allows for the recovery of much of the
sharpness that is now expected to be lost when implemented with memristors. It
should be noted that a reduced range is not necessarily a problem, as the
circuits before the CAM cell in the signal chain can be designed to output in
the operating range of the CAM cell, and may even have their own headroom
requirements that make a wider window unnecessary.

| Minimum | Wide | Native
---|---|---|---
NMOS Width | $220\text{\,}\mathrm{nm}$ | $1\text{\,}\mathrm{\SIUnitSymbolMicro m}$ | $420\text{\,}\mathrm{nm}$
NMOS Length | $180\text{\,}\mathrm{nm}$ | $180\text{\,}\mathrm{nm}$ | $500\text{\,}\mathrm{nm}$
PMOS Width | $220\text{\,}\mathrm{nm}$ | $1\text{\,}\mathrm{\SIUnitSymbolMicro m}$ | $220\text{\,}\mathrm{nm}$
PMOS Length | $180\text{\,}\mathrm{nm}$ | $180\text{\,}\mathrm{nm}$ | $180\text{\,}\mathrm{nm}$

TABLE I: Chart of transistor sizes in the three designs that were simulated.

###  IV-B Assessment

To assess the window width, static DC simulations of the circuits were run.
The circuits were supplied at $1.8\text{\,}\mathrm{V}$ and the inputs swept
from $0\text{\,}\mathrm{V}$ to the supply voltage, measuring the current
measured at the output. This was repeated for geometrically spaced values of
$1\text{\,}\mathrm{k\SIUnitSymbolOhm}$ to
$100\text{\,}\mathrm{k\SIUnitSymbolOhm}$ for the dynamic element. In all cases
the output was connected to a $100\text{\,}\mathrm{k\SIUnitSymbolOhm}$ dummy
load. The window widths were calculated using the same differential method
mentioned earlier.

Figure 8: Top left: A graph of the IV characteristics of the minimum circuit,
sweeping M1 from $1\text{\,}\mathrm{k\SIUnitSymbolOhm}$ to
$100\text{\,}\mathrm{k\SIUnitSymbolOhm}$. Top centre: A graph of an identical
sweep of M1 with the wide circuit. Top right: A graph of an identical sweep of
M1 with the native circuit. Bottom: A graph of the window width of all three
circuits as a function of M1.

In the circuit with minimum size input transistors, the window width was
drastically reduced. Further to this, the range of values for the lower
thresholds was roughly half the maximum window width. While the transitions
were sharper, this reduced range represents a catastrophic loss of
functionality, as a narrow window can only be set in a
$100\text{\,}\mathrm{mV}$ range. The wide input stage circuit performed much
better, losing less maximum window width and retaining most of the threshold
sweep of the PCB model. The sharpness of the transitions was also superior to
the minimum width circuit, due to the higher gain of the input FETs. The
native input stage circuit displayed a wider maximum window width than even
the wide circuit, although the minimum size PMOS left it with a lower
threshold range comparable to the minimum circuit. The sharpness of
transitions in the native circuit were noticeably worse. As one might expect
from the lower threshold voltages of native devices, the window of the native
circuit was much loser to $0\text{\,}\mathrm{V}$ than the others, which were
almost centred in the supply range. In all circuits, plotting the window width
as a function of the logarithm of M1 showed less nonlinearity than lower
threshold of the PCB model.

Figure 9: Top left: A graph of the IV characteristics of the minimum circuit,
sweeping M2 from $1\text{\,}\mathrm{k\SIUnitSymbolOhm}$ to
$100\text{\,}\mathrm{k\SIUnitSymbolOhm}$. Top centre: A graph of an identical
sweep of M2 with the wide circuit. Top right: A graph of an identical sweep of
M2 with the native circuit. Bottom: A graph of the window width of all three
circuits as a function of M2.

The differences in the behaviour of the top threshold between the three
circuits was less pronounced. All three were able to bring the top threshold
to within $100\text{\,}\mathrm{mV}$ of the bottom threshold. The only
significant differences were the inability of the minimum circuit to reach the
maximum window widths of the other two, and the less defined transitions of
the native circuit.

###  IV-C Energy

Figure 10: A graph of the test energy of a single simulated CAM cell, as a
function of input voltage.

To estimate the energy required to test a single sample, a second gate was
added to each of the output transistors as an output enable control, and a
transient analysis simulation was run. In this test, the circuit began with
the supply energised, the output disabled, and the input parked at either
supply or ground. The minimum and wide circuits were parked ant ground and the
native circuit parked at supply. The input was brought to the test value and
held there for $2.35\text{\,}\mathrm{ns}$ to settle. The enable signal was
then pulsed for $450\text{\,}\mathrm{ps}$. $200\text{\,}\mathrm{ps}$ after the
enable pulse ends, the input is returned to its parked state. The energy was
calculated by integrating the sum of the instantaneous power at the input, the
enable input, and the supply. As might be expected for an analysis that
includes the output current, the test energy of a hit was the peak energy in
all cases. Curiously, the miss energy on the opposite side of the window to
the parked state was substantially higher than the miss energy on the same
side of the window. This is likely because the act of bringing the input
signal to the test voltage and back causes the input to pass through both
input inverter’s crossover points. This would cause a small surge of current
each time, resulting in the observed plateau.

| Minimum | Wide | Native
---|---|---|---
Hit Voltage | $900\text{\,}\mathrm{mV}$ | $900\text{\,}\mathrm{mV}$ | $600\text{\,}\mathrm{mV}$
$25\text{\,}\mathrm{\SIUnitSymbolCelsius}$ | $42.36\text{\,}\mathrm{fJ}$ | $57.44\text{\,}\mathrm{fJ}$ | $61.75\text{\,}\mathrm{fJ}$
$37\text{\,}\mathrm{\SIUnitSymbolCelsius}$ | $42.92\text{\,}\mathrm{fJ}$ | $58.30\text{\,}\mathrm{fJ}$ | $62.41\text{\,}\mathrm{fJ}$
Fast/Fast Corner | $61.26\text{\,}\mathrm{fJ}$ | $76.11\text{\,}\mathrm{fJ}$ | $86.51\text{\,}\mathrm{fJ}$
Slow/Slow Corner | $29.34\text{\,}\mathrm{fJ}$ | $44.48\text{\,}\mathrm{fJ}$ | $44.55\text{\,}\mathrm{fJ}$
Miss Voltage | $1.3\text{\,}\mathrm{V}$ | $1.5\text{\,}\mathrm{V}$ | $1.2\text{\,}\mathrm{V}$
$25\text{\,}\mathrm{\SIUnitSymbolCelsius}$ | $18.75\text{\,}\mathrm{fJ}$ | $39.43\text{\,}\mathrm{fJ}$ | $12.54\text{\,}\mathrm{fJ}$
$37\text{\,}\mathrm{\SIUnitSymbolCelsius}$ | $19.39\text{\,}\mathrm{fJ}$ | $39.78\text{\,}\mathrm{fJ}$ | $13.77\text{\,}\mathrm{fJ}$
Fast/Fast Corner | $27.40\text{\,}\mathrm{fJ}$ | $40.88\text{\,}\mathrm{fJ}$ | $27.88\text{\,}\mathrm{fJ}$
Slow/Slow Corner | $15.22\text{\,}\mathrm{fJ}$ | $37.99\text{\,}\mathrm{fJ}$ | $4.738\text{\,}\mathrm{fJ}$

Maximum Window Width at | Minimum | Wide | Native
---|---|---|---
$25\text{\,}\mathrm{\SIUnitSymbolCelsius}$ | $436\text{\,}\mathrm{mV}$ | $558\text{\,}\mathrm{mV}$ | $606\text{\,}\mathrm{mV}$
$37\text{\,}\mathrm{\SIUnitSymbolCelsius}$ | $441\text{\,}\mathrm{mV}$ | $568\text{\,}\mathrm{mV}$ | $610\text{\,}\mathrm{mV}$
Fast/Fast Corner | $523\text{\,}\mathrm{mV}$ | $630\text{\,}\mathrm{mV}$ | $690\text{\,}\mathrm{mV}$
Slow/Slow Corner | $341\text{\,}\mathrm{mV}$ | $482\text{\,}\mathrm{mV}$ | $511\text{\,}\mathrm{mV}$

TABLE II: Top: A chart of test energies at typical hit/miss voltages for
several process corners. Note that the difference in hit/miss voltage between
the circuit variants make this data less useful for comparing the variants. It
is more intended to show the response of each circuit to process variation and
temperature. Bottom: A chart of the maximum window width at several process
corners

Further simulations were run at relevant process corners. A corner is a set of
environmental or process conditions that might affect circuit performance.
Each of the circuits was simulated at four corner conditions: room
temperature, body temperature, P/NMOS above specified gain (Fast/Fast), and
P/NMOS below specified gain (Slow/Slow). A hit and a miss voltage were chosen
for each circuit, to give estimates for a typical use case. The variation with
temperature was minimal, but the effect of process variation was substantial,
with a Fast/Fast hit dissipating almost twice the energy of a Slow/Slow hit.
As the name suggests, a corner is the extreme edge of what one can expect out
of the technology, but the variation on display here is sufficient enough to
warrant further investigation.

###  IV-D Process Variation

To obtain a clearer picture of the impact of process variation, a Monte Carlo
analysis was conducted. This approach uses a large number of simulations with
randomised process variation to provide a statistical model of the expected
impact. In this test, the characteristic being monitored is the maximum window
width, calculated using the same differential method used earlier. 250
simulations were run for each circuit.

| Minimum | Wide | Native
---|---|---|---
$\mu$ | $436\text{\,}\mathrm{mV}$ | $559\text{\,}\mathrm{mV}$ | $606\text{\,}\mathrm{mV}$
$\sigma$ | $29.9\text{\,}\mathrm{mV}$ | $23.6\text{\,}\mathrm{mV}$ | $33.0\text{\,}\mathrm{mV}$

Figure 12: Top: A histogram plot and fit of a 250 point Monte Carlo simulation
of the maximum window width. Bottom: A table of the fit parameters, assuming a
normal distribution.

The resulting histograms of window width show a significant level of variation
in the minimum and native circuits. If an error in fabrication causes a gate
element to be $20\text{\,}\mathrm{nm}$ narrower than intended, the
proportional error will be much larger on a minimum size FET than a wider one,
so greater variance on the minimum size circuit is to be expected. Why the
native circuit has slightly greater variance is not entirely clear, as the
larger minimum size of the native FETs should result in marginally less
variance, but the low doping level of the native devices likely makes them
more vulnerable to fabrication errors there. The wide circuit showed the least
variance, both in absolute terms and in proportion of average maximum window
width.

With the validity of the model demonstrated, the next was to assess the power
dissipation of the circuit. Simulation of the circuit using the TSMC180BCD PDK
was conducted for this purpose. Unlike the previous tests, these test used
much lower values for the balancing and dynamic resistors, since an integrated
resistor with a value of $1\text{\,}\mathrm{M\SIUnitSymbolOhm}$ would be
prohibitively large. $10\text{\,}\mathrm{k\SIUnitSymbolOhm}$ and
$1-$100\text{\,}\mathrm{k\SIUnitSymbolOhm}$$ balancing and dynamic resistors
were used. In addition to this, an extra gate was added to both transistors in
the output stage, to allow the output to be disabled when the input was being
adjusted or the circuit shut down. The energy of a test was obtained by
bringing the input from its parked state to the test value and then enabling
the circuit briefly after the input stages settled.

##  V Discussions and Conclusions

As the ratio between dynamic and balancing elements is the only control
parameter that has a significant effect, M1 and R1 could swap positions. This
would allow for both thresholds to have identical control methods, at the
trivial cost of inverting the control of one threshold. With both dynamic
elements connected to ground, the devices could be written through the body
diodes of the neighbouring NMOS, although this method has yet to be
demonstrated. The circuit could be further improved by switching to a smaller
technology node, such as $22\text{\,}\mathrm{nm}$. Such a switch would also
make the somewhat optimistic control timings described in this work easier to
implement.

The circuit considered in this paper demonstrates a highly controllable and
flexible analogue content addressable memory cell with acceptable power
dissipation. The design has similar area requirements to the work by Can Li et
al.[16], with similar functionality. This work has inferior energy
dissipation, but the thresholds of the window are sharper and more
controllable despite using a smaller range of dynamic element states, with one
fifth the ration between minimum and maximum dynamic element values. Further,
this work uses a current output rather than a match line. While this is a
major factor in the higher energy dissipation, it gives an array of these
cells an analogue output. Aside from the obvious use in full analogue neural
networks, this also allows for a template matching array based on these cells
to tolerate irregularities in the input, such as might be found in neural
spike sorting. Compared to the reconfigurable logic gates this work was
developed from[15], this work demonstrates a greater degree of controllability
for a similar device count and area. While this work does not achieve a
comprehensive improvement over existing works, it achieves appreciable
improvements in areas relevant to developing fields.

## References

  * [1] R. Karam, R. Puri, S. Ghosh, and S. Bhunia, “Emerging trends in design and applications of memory-based computing and content-addressable memories,” _Proceedings of the IEEE_ , vol. 103, no. 8, pp. 1311–1330, 2015, DOI: 10.1109/JPROC.2015.2434888.
  * [2] G. Pedretti, C. Graves, S. Serebryakov, R. Mao, X. Sheng, M. Foltin, C. Li, and J. W. Strachan, “Tree-based machine learning performed in-memory with memristive analog cam,” _Nature Communications_ , vol. 12, 10 2021, DOI: 10.1038/s41467-021-25873-0.
  * [3] C.-S. Lin, J.-C. Chang, and B.-D. Liu, “A low-power precomputation-based fully parallel content-addressable memory,” _IEEE Journal of Solid-State Circuits_ , vol. 38, no. 4, pp. 654–662, 2003, DOI: 10.1109/JSSC.2003.809515.
  * [4] H. Liu, “Routing table compaction in ternary cam,” _IEEE Micro_ , vol. 22, no. 1, pp. 58–64, 2002, DOI: 10.1109/40.988690.
  * [5] I. Arsovski, T. Chandler, and A. Sheikholeslami, “A ternary content-addressable memory (tcam) based on 4t static storage and including a current-race sensing scheme,” _IEEE Journal of Solid-State Circuits_ , vol. 38, no. 1, pp. 155–158, 2003, DOI: 10.1109/JSSC.2002.806264.
  * [6] C. E. Graves, C. Li, X. Sheng, D. Miller, J. Ignowski, L. Kiyama, and J. P. Strachan, “In-memory computing with memristor content addressable memories for pattern matching,” _Advanced Materials_ , vol. 32, no. 37, p. 2003437, 2020, DOI: https://doi.org/10.1002/adma.202003437.
  * [7] Y. Pan, P. Foster, J. Huang, A. Serb, and T. Prodromakis, “An rram-based associative memory cell,” 2021.
  * [8] M. Hock, A. Hartel, J. Schemmel, and K. Meier, “An analog dynamic memory array for neuromorphic hardware,” in _2013 European Conference on Circuit Theory and Design (ECCTD)_ , 2013, pp. 1–4, DOI: 10.1109/ECCTD.2013.6662229.
  * [9] H. Graf and L. Jackel, “Analog electronic neural network circuits,” _IEEE Circuits and Devices Magazine_ , vol. 5, no. 4, pp. 44–49, 1989, DOI: 10.1109/101.29902.
  * [10] X. Yin, C. Li, Q. Huang, L. Zhang, M. Niemier, X. Hu, C. Zhuo, and K. Ni, “Fecam: A universal compact digital and analog content addressable memory using ferroelectric,” 04 2020.
  * [11] R. Rajaei, M. M. Sharifi, A. Kazemi, M. Niemier, and X. S. Hu, “Compact single-phase-search multistate content-addressable memory design using one fefet/cell,” _IEEE Transactions on Electron Devices_ , vol. 68, no. 1, pp. 109–117, 2021, DOI: 10.1109/TED.2020.3039477.
  * [12] ——, “Compact single-phase-search multistate content-addressable memory design using one fefet/cell,” _IEEE Transactions on Electron Devices_ , vol. 68, no. 1, pp. 109–117, 2021, DOI: 10.1109/TED.2020.3039477.
  * [13] G. Pedretti, C. E. Graves, T. Van Vaerenbergh, S. Serebryakov, M. Foltin, X. Sheng, R. Mao, C. Li, and J. P. Strachan, “Differentiable content addressable memory with memristors,” _Advanced Electronic Materials_ , vol. 8, no. 8, p. 2101198, 2022, DOI: https://doi.org/10.1002/aelm.202101198.
  * [14] R. Rajaei, M. M. Sharifi, A. Kazemi, M. Niemier, and X. S. Hu, “Compact single-phase-search multistate content-addressable memory design using one fefet/cell,” _IEEE Transactions on Electron Devices_ , vol. 68, no. 1, pp. 109–117, 2021, DOI: 10.1109/TED.2020.3039477.
  * [15] A. Serb, A. Khiat, and T. Prodromakis, “Seamlessly fused digital-analogue reconfigurable computing using memristors,” _Nature Communications_ , vol. 9, 12 2018, DOI: 10.1038/s41467-018-04624-8.
  * [16] C. Li, C. Graves, X. Sheng, D. Miller, M. Foltin, G. Pedretti, and J. W. Strachan, “Analog content-addressable memories with memristors,” _Nature Communications_ , vol. 11, 04 2020, DOI: 10.1038/s41467-020-15254-4.
  * [17] P. Foster, J. Huang, A. Serb, S. Stathopoulos, C. Papavassiliou, and T. Prodromakis, “An fpga-based system for generalised electron devices testing,” _Scientific Reports_ , 2022, DOI: 10.1038/s41598-022-18100-3.
  * [18] Toshiba, _SSM6L36TU LF Datasheet_ , 2014.
  * [19] A. Zaffora, F. Di Franco, R. Macaluso, and M. Santamaria, “17 - tio2 in memristors and resistive random access memory devices,” in _Titanium Dioxide (TiO 2) and Its Applications_, ser. Metal Oxides, F. Parrino and L. Palmisano, Eds. Elsevier, 2021, pp. 507–526, DOI: https://doi.org/10.1016/B978-0-12-819960-2.00020-1.


#  A novel multi-step method for the partial pole assignment in symmetric
quadratic pencil with time delay

Qing Liu<EMAIL_ADDRESS>School of Mathematics and Shing-Tung Yau Center,
Southeast University, Nanjing 211189, P. R. China.  Nanjing Center for Applied
Mathematics, Nanjing 211135, P. R. China.

###### Abstract

In this paper, we study the partial pole assignment problem in symmetric
quadratic pencil with time delay. A novel multi-step method is proposed to
solve this problem, resulting in the undesired eigenvalues being moved to
desired values, and the remaining eigenvalues unchanged. By establishing a new
matrix equality relation and using a multi-step method, the problem is
transformed into solving linear systems with low order. Specifically, assuming
that there are $p$ undesired eigenvalues requiring reassigned, the size of the
linear system we finally solved is $p^{2}.$ Notably, the method demonstrates
high efficiency for large systems with only a few poles requiring reassigned.
Numerical examples are provided to illustrate the effectiveness of the
proposed method.

###### keywords:

Inverse problem; Second-order linear system; Partial pole assignment; Multi-
step method; Time delay.

##  1  Introduction

In structural dynamics (e.g., bridges, buildings, airplanes and automobiles),
the finite element method is used to discretize the damped linear system with
$n$ degrees of freedom, and the second-order linear differential equation with
constant coefficients is generated as follows:

$M{\kern 1.0pt}\ddot{x}(t)+C{\kern 1.0pt}\dot{x}(t)+Kx(t)=f(t-\tau),$ (1)

where $M,C,K\in{\mathbb{R}^{n\times n}}$ are the symmetric mass matrix,
damping matrix and stiffness matrix with $M$ positive definite,
$x(t)\in\mathbb{R}^{n}$ is the displacement vector, $f(t-\tau)$ is the
external force control or control vector and $\tau$ is the time delay between
the measurements of the state and the actuation of the control. Let
$f(t-\tau)=0$, then (1) may be solved by using the method of separation of
variables. Substituting $x(t)=x{e^{\lambda t}}$, where
$\lambda\in{\mathbb{C}}$, $x\in{\mathbb{C}^{n}}$, into (1) yields the
quadratic eigenvalue problem of the open-loop system:

$P(\lambda)x:=\left({\lambda^{2}}M+\lambda C+K\right)x=0,$ (2)

where $P(\lambda)={\lambda^{2}}M+\lambda C+K$ is called the open-loop
quadratic pencil, $\lambda$ is referred to as the eigenvalue or complex
frequency or pole, and $x$ is called the eigenvector or vibration mode. In
practical engineering problems, only a few poles are unstable and lead to the
system resonance. In order to prevent system instability or resonance, it is
essential to modify the unstable poles of $P(\lambda)$ through feedback
control. At the same time, it is crucial to ensure that the rest of the
system’s eigenstructure remains unaltered, thereby preserving the property of
no spill-over. This leads to the partial quadratic pole assignment problem [1,
2, 3, 4].

The system can be controlled by the external force $f(t-\tau)=Bu(t-\tau)$, and
the corresponding equation of state is described by

$M{\kern 1.0pt}\ddot{x}(t)+C{\kern 1.0pt}\dot{x}(t)+Kx(t)=Bu(t-\tau),$ (3)

where $B\in{\mathbb{R}^{n\times m}}$ is the full column rank control matrix
and $u(t-\tau)\in{\mathbb{R}^{m}}$ is the feedback control vector. If $m=1$,
the system (3) is reduced into the single-input control system, and if $m>1$,
it is called the multi-input control system. In this paper, $u(t-\tau)$ is
chosen as the displacement-velocity feedback control

$u(t-\tau)=G^{\top}x(t-\tau)+{F^{\top}}\dot{x}(t-\tau),$ (4)

where $G,F\in\mathbb{R}^{n\times m}$ are the displacement feedback matrix and
velocity feedback matrix, respectively. Substituting (4) into (3), the
following second-order closed-loop system can be obtained:

$M{\kern 1.0pt}\ddot{x}(t)+C{\kern 1.0pt}\dot{x}(t)+K{\kern
1.0pt}x(t)=B\left({F^{\top}}\dot{x}(t-\tau)+{G^{\top}}x(t-\tau)\right).$ (5)

It follows that the corresponding quadratic eigenvalue problem with time delay
is

${P_{\tau}}(\lambda)x:=\left[{\lambda^{2}}M+\lambda\left(C-B{F^{\top}}e^{-\lambda\tau}\right)+\left(K-B{G^{\top}}e^{-\lambda\tau}\right)\right]x=0,$
(6)

where
${P_{\tau}}(\lambda)={\lambda^{2}}M+\lambda\left(C-B{F^{\top}}e^{-\lambda\tau}\right)+\left(K-B{G^{\top}}e^{-\lambda\tau}\right)$.
Suppose that $\left\\{{{\lambda_{i}}}\right\\}_{i=1}^{p}(p<2n)$ are undesired
poles of the second-order system (3), which need to be reassigned to the
desired poles $\left\\{{{\mu_{i}}}\right\\}_{i=1}^{p}$. This leads to the
following problem, known as the partial quadratic pole assignment problem with
time delay.

Problem 1. Given the symmetric matrices of the second-order system
$M,C,K\in\mathbb{R}^{n\times n}$ with $M$ positive definite, the full column
rank control matrix $B\in{\mathbb{R}^{n\times m}}$, the time delay $\tau>0$,
the self-conjugate subset
$\left\\{{{\lambda_{i}}}\right\\}_{i=1}^{p}\left({p<2n}\right)$ of the open-
loop spectrum $\left\\{{{\lambda_{i}}}\right\\}_{i=1}^{2n}$ and the
corresponding eigenvector set $\left\\{{{x_{i}}}\right\\}_{i=1}^{p}$, and the
desired self-conjugate set $\left\\{{{\mu_{i}}}\right\\}_{i=1}^{p}$. Find the
state feedback matrices $F,G$ $\in{\mathbb{R}^{n\times m}}$ such that the
closed-loop delayed pencil ${P_{\tau}}(\lambda)$ has the desired eigenvalues
$\left\\{{{\mu_{i}}}\right\\}_{i=1}^{p}$ and the eigenpairs
$\left\\{{\left({{\lambda_{i}},{x_{i}}}\right)}\right\\}_{i=p+1}^{2n}$.

If the system (3) is partially controllable [5] with respect to the
eigenvalues $\lambda=\lambda_{i}(i=1,2,\ldots,p)$, then

${\rm{rank}}\big{\\{}{{\lambda^{2}}M+\lambda C+K,B}\big{\\}}=n.$

In this paper, we assume that $\left\\{{{\lambda_{i}}}\right\\}_{i=1}^{p}$ and
$\left\\{{{\mu_{i}}}\right\\}_{i=1}^{p}$ are all distinct, the system (3) is
partially controllable with respect to
$\left\\{{{\lambda_{i}}}\right\\}_{i=1}^{p}$, and

$\left\\{\mu_{i}\right\\}_{i=1}^{p}\cap\left\\{\lambda_{i}\right\\}_{i=1}^{2n}=\emptyset,\
\left\\{\lambda_{i}\right\\}_{i=1}^{p}\cap\left\\{\lambda_{i}\right\\}_{i=p+1}^{2n}=\emptyset.$
(7)

Let

$\Lambda={\rm{diag}}\big{(}\lambda_{1},\lambda_{2},\ldots,\lambda_{2n}\big{)},\
X=\big{[}x_{1},x_{2},\ldots,x_{2n}\big{]},$
$\Lambda_{1}={\rm{diag}}\big{(}\lambda_{1},\lambda_{2},\ldots,\lambda_{p}\big{)},\
\Lambda_{2}={\rm{diag}}\big{(}\lambda_{p+1},\lambda_{p+2},\ldots,\lambda_{2n}\big{)},$
$X_{1}=\big{[}x_{1},x_{2},\ldots,x_{p}\big{]},\
X_{2}=\big{[}x_{p+1},x_{p+2},\ldots,x_{2n}\big{]}.$

Datta et al [6] derived the following three orthogonality relations

$\Lambda X^{\top}MX\Lambda-X^{\top}KX=D_{1},$ (8) $\Lambda
X^{\top}CX\Lambda+\Lambda X^{\top}KX+X^{\top}KX\Lambda=D_{2},$ (9) $\Lambda
X^{\top}MX+X^{\top}MX\Lambda+X^{\top}CX=D_{3},$ (10)

where $D_{1},D_{2},D_{3}\in{\mathbb{C}^{2n\times 2n}}$ are diagonal matrices.
Via orthogonality relation (8), Datta et al [6] presented the explicit
solution of feedback control matrices $F$ and $G$ for the partial quadratic
pole assignment problem for the single-input system. Ram and Elhay [7]
generalized it to the multi-input system such that a multi-step method for the
partial quadratic pole assignment problem is developed. However, this method
cannot reassign zero or near zero poles and needs to solve $(m\cdot p)$
$n$-order linear systems. Based on the receptance method [8], Ram et al [9]
proposed an algorithm for the partial quadratic pole assignment problem with
time delay for the single-input system. Bai et al [10, 11], Ram and
Mottershead [12], Chen and Xie [13], and Richiedei et al [14] developed the
receptance methods for the partial quadratic pole assignment problems for the
multi-input system. However, the receptance matrix needs to be measured by
modal tests, and the receptance matrix is sensitive to the test noise [8, 15].
Mao [16] provided a method for solving the partial quadratic pole assignment
problem without using the receptance matrix. However, this method needs to
solve the Sylvester equation. Liu and Yuan [17] developed a multi-step method
for solving the partial quadratic pole assignment problem with time delay.
However, this method needs to solve $(m\cdot p)$ $n$-order linear systems,
which the computational cost is relatively expensive for the large-scale
system.

In this paper, we study an efficient numerical method for the partial pole
assignment in symmetric quadratic pencil with time delay. The main innovations
presented in this paper can be summarized as follows. Firstly, we provide an
explicit solution to Problem 1 for the single-input system, utilizing the
third orthogonality relation (10) and the inverse of the Cauchy matrix. This
method involves only the multiplication of matrices and vectors. Secondly, for
the multi-input system, we establish a new connection between system matrices,
undesired eigenvalues and corresponding eigenvectors, as well as desired
eigenvalues and control vectors. This enables us to develop a novel multi-step
method that transforms Problem 1 into solving $p^{2}$-order linear systems,
and does not involve solving $n$-order linear systems. This approach proves to
be highly efficient for large-scale systems, as it only requires reassigning a
small number of poles, i.e. it is particularly suitable for $p\ll n$.

The remaining of this paper is organized as follows. In section 2, we present
an explicit solution to Problem 1 for the single-input system. In section 3, a
novel multi-step method is proposed to solve Problem 1 for the multi-input
system. Numerical examples are presented in section 4. Finally, we draw some
conclusions in section 5.

##  2 Single-input control

In this section, we consider the single-input control system, which means
$m=1$,

$B=b\in{\mathbb{R}^{n}},\ F=f\in{\mathbb{R}^{n}},\ G=g\in{\mathbb{R}^{n}}.$

To begin with, we provide the following three lemmas.

######  Lemma 1.

[5] The single-input control system (3) is partially controllable with respect
to the eigenvalues ${{\lambda_{i}}}$ if and only if $b^{\top}x_{i}\neq 0\ $
$(i=1,2,\ldots,p)$.

According to the orthogonality relation (10), we can obtain

$\Lambda_{1}X_{1}^{\top}MX_{2}+X_{1}^{\top}MX_{2}\Lambda_{2}+X_{1}^{\top}CX_{2}=0.$
(11)

Therefore, the following lemma can be verified.

######  Lemma 2.

[10] For arbitrary $\beta\in\mathbb{C}^{p}$, define

$f=M{X_{1}}\beta,\ g=\left(M{X_{1}}{\Lambda_{1}}+C{X_{1}}\right)\beta,$ (12)

then the closed-loop delayed pencil ${P_{\tau}}(\lambda)$ has the eigenpairs
$\left\\{{\left({{\lambda_{i}},{x_{i}}}\right)}\right\\}_{i=p+1}^{2n}$, that
means

$M{X_{2}}\Lambda_{2}^{2}+C{X_{2}}{\Lambda_{2}}-bf^{\top}{X_{2}}{\Lambda_{2}}e^{-\tau\Lambda_{2}}+K{X_{2}}-bg^{\top}{X_{2}}e^{-\tau\Lambda_{2}}=0.$

######  Remark 1.

Lemma 2 indicates that the feedback vectors $f$ and $g$ defined by (12) can
make the closed-loop delayed pencil
${P_{\tau}}(\lambda)={\lambda^{2}}M+\lambda\left(C-b{f^{\top}}e^{-\lambda\tau}\big{)}+\big{(}K-b{g^{\top}}e^{-\lambda\tau}\right)$
keep the remaining eigenstructure of the original system unchanged, i.e., the
no spill-over property is preserved.

Assume that $\left\\{(\mu_{i},y_{i})\right\\}_{i=1}^{p}$ are the eigenpairs of
the closed-loop delayed pencil ${P_{\tau}}(\lambda)$, define

$\Sigma_{1}={\rm{diag}}\big{(}\mu_{1},\mu_{2},\ldots,\mu_{p}\big{)},\
Y_{1}=\big{[}y_{1},y_{2},\ldots,y_{p}\big{]},$
$H=\big{(}h_{ij}\big{)}=\Lambda_{1}X_{1}^{\top}MY_{1}+X_{1}^{\top}MY_{1}\Sigma_{1}+X_{1}^{\top}CY_{1}.$
(13)

######  Lemma 3.

[17] If the single-input control system (3) is partially controllable with
respect to the eigenvalues $\left\\{\lambda_{i}\right\\}_{i=1}^{p}$,
$\left\\{{{\lambda_{i}}}\right\\}_{i=1}^{p}$ and
$\left\\{{{\mu_{i}}}\right\\}_{i=1}^{p}$ are all distinct and satisfy (7), and
$\left\\{y_{i}\right\\}_{i=1}^{p}$ are the solutions of the linear equations

$\left(\mu_{i}^{2}M+\mu_{i}C+K\right)y_{i}=b,\ i=1,2,\ldots,p,$

then $H$ is nonsingular, and

$H=\tilde{H}\hat{H},$

where

$\tilde{H}={\rm{diag}}(b^{\top}x_{1},{b^{\top}}x_{2},\ldots,b^{\top}x_{p}),\
\hat{H}=\left({\begin{array}[]{*{20}{c}}\frac{1}{\mu_{1}-\lambda_{1}}&\cdots&\frac{1}{\mu_{p}-\lambda_{1}}\\\
\cdots&\cdots&\cdots\\\
\frac{1}{\mu_{1}-\lambda_{p}}&\cdots&\frac{1}{\mu_{p}-\lambda_{p}}\end{array}}\right).$
(14)

From Lemma 2, solving Problem 1 is transformed into determining vector $\beta$
in (12) such that

$MY_{1}\Sigma_{1}^{2}+CY_{1}\Sigma_{1}-bf^{\top}Y_{1}\Sigma_{1}e^{-\tau\Sigma_{1}}+KY_{1}-bg^{\top}Y_{1}e^{-\tau\Sigma_{1}}=0.$
(15)

Substituting $f$ and $g$ defined in (12) into (15), and according to the
definition of $H$ in (13), we can derive

$\displaystyle MY_{1}\Sigma_{1}^{2}+CY_{1}\Sigma_{1}+KY_{1}$
$\displaystyle=b\beta^{\top}\left(\Lambda_{1}X_{1}^{\top}MY_{1}+X_{1}^{\top}MY_{1}\Sigma_{1}+X_{1}^{\top}CY_{1}\right)e^{-\tau\Sigma_{1}}$
$\displaystyle=b\beta^{\top}He^{-\tau\Sigma_{1}}:=b\gamma,$

where $\gamma=\beta^{\top}He^{-\tau\Sigma_{1}}$. Moreover, the vector $\gamma$
is related to the eigenvector $Y_{1}$ of the closed-loop delayed pencil
${P_{\tau}}(\lambda)$. In order to obtain $Y_{1}$, we can calculate the
eigenvectors $\left\\{y_{i}\right\\}_{i=1}^{p}$ from the linear equations

$\left(\mu_{i}^{2}M+\mu_{i}C+K\right)y_{i}=b,\ i=1,2,\ldots,p,$ (16)

which corresponds to the selection $\gamma=[1,1,\ldots,1]\in\mathbb{R}^{p}$.
Therefore, parameter vector $\beta$ satisfies

$\beta^{\top}H=[1,1,\ldots,1]e^{\tau\Sigma_{1}}.$ (17)

According to Lemma 3, the linear system (17) has a unique solution, then we
can obtain the following result.

######  Theorem 1.

If the single-input control system (3) is partially controllable with respect
to the eigenvalues $\left\\{\lambda_{i}\right\\}_{i=1}^{p}$,
$\left\\{{{\lambda_{i}}}\right\\}_{i=1}^{p}$ and
$\left\\{{{\mu_{i}}}\right\\}_{i=1}^{p}$ are all distinct and satisfy (7), and
$\left\\{y_{i}\right\\}_{i=1}^{p}$ are the solutions of (16), then Problem 1
has a unique solution, which can be expressed by (12), where $\beta$ is the
solution of the linear system (17).

In fact, we need not to solve $p$ linear systems (16). Since $\hat{H}$ defined
in (14) is a Cauchy matrix, define $T=\big{(}t_{ij}\big{)}_{p\times
p}=\hat{H}^{-1}$ and
$\beta=\big{[}\beta_{1},\beta_{2},\ldots,\beta_{p}\big{]}^{\top}$, based on
the inverse of the Cauchy matrix [18], we can derive

$t_{ij}=\frac{\prod\limits_{k=1}^{p}(\lambda_{j}-\mu_{k})\prod\limits_{k=1}^{p}(\mu_{i}-\lambda_{k})}{(\lambda_{j}-\mu_{i})\prod\limits_{k=1,k\neq
i}^{p}(\mu_{i}-\mu_{k})\prod\limits_{k=1,k\neq
j}^{p}(\lambda_{j}-\lambda_{k})}.$ (18)

Therefore, the explicit expression of $\beta$ in (12) is given by

$\beta_{j}=\frac{1}{b^{\top}x_{j}}\sum\limits_{i=1}^{p}t_{ij}e^{\tau\mu_{i}}.$
(19)

Substituting $t_{ij}$ defined in (18) into (19), we can obtain

$\beta_{j}=\frac{1}{b^{\top}x_{j}}\frac{\prod\limits_{k=1}^{p}(\lambda_{j}-\mu_{k})}{\prod\limits_{k=1,k\neq
j}^{p}(\lambda_{j}-\lambda_{k})}\sum\limits_{i=1}^{p}\frac{\prod\limits_{k=1}^{p}(\mu_{i}-\lambda_{k})}{(\lambda_{j}-\mu_{i})\prod\limits_{k=1,k\neq
i}^{p}(\mu_{i}-\mu_{k})}e^{\tau\mu_{i}}.$ (20)

######  Remark 2.

The explicit expression of $\beta$ in (12) is easy to implement without
solving any linear system. If time delay $\tau=0$, (20) can be further
simplified. Datta et al [6] prove that

$\sum\limits_{i=1}^{p}\frac{\prod\limits_{k=1,k\neq
j}^{p}(\mu_{i}-\lambda_{k})}{\prod\limits_{k=1,k\neq
i}^{p}(\mu_{i}-\mu_{k})}=1,$

then,

$\beta_{j}=\frac{1}{b^{T}x_{j}}(\mu_{j}-\lambda_{j})\prod\limits_{k=1,k\neq
j}^{p}\frac{\lambda_{j}-\mu_{k}}{\lambda_{j}-\lambda_{k}}.$

It is easy to prove that if the complex eigenvalues of $\Lambda_{1}$ and
$\Sigma_{1}$ appear as conjugate pairs, the velocity feedback vector $f$ and
displacement feedback vector $g$ calculated by this method are both real.
Based on Theorem 1, we can summarize the following algorithm.

Algorithm 1 A direct method for Problem 1 by single-input control.
---
Input:
The symmetric matrices $M,C\in\mathbb{R}^{n\times n}$ with $M$ positive
definite;
The control vector $b\in{\mathbb{R}^{m}}$ and the time delay $\tau>0$;
The self-conjugate eigenpairs $\left\\{(\lambda_{i},x_{i})\right\\}_{i=1}^{p}$
and a self-conjugate set $\left\\{{{\mu_{i}}}\right\\}_{i=1}^{p}$.
Output:
State feedback real vectors $f$ and $g$.
1: Form $\Lambda_{1}={\rm{diag}}(\lambda_{1},\lambda_{2},\ldots,\lambda_{p})$
and $X_{1}=[x_{1},x_{2},\ldots,x_{p}]$;
2: For $j=1,2,\ldots,p$, calculate $\beta_{j}$ according to (20);
3: Form $\beta=\big{[}\beta_{1},\beta_{2},\ldots,\beta_{p}\big{]}^{\top}$;
4: Compute $f=MX_{1}\beta,\ g=\left(MX_{1}\Lambda_{1}+CX_{1}\right)\beta$.

##  3  Multi-input control

In this section, we consider Problem 1 for the multi-input control system,
which means $m>1$. The closed-loop system (5) can be written as

$M\ddot{x}(t)+C\dot{x}(t)+Kx(t)=\sum\limits_{k=1}^{m}b_{k}\left(f_{k}^{\top}\dot{x}(t-\tau)+g_{k}^{\top}x(t-\tau)\right),$

where $b_{k}$, $f_{k}$, and $g_{k}$ are the $k$-th columns of $B$, $F$ and
$G$, respectively. The corresponding closed-loop delayed pencil is given by

$P_{\tau}(\lambda)=\lambda^{2}M+\lambda\Big{(}C-\sum\limits_{k=1}^{m}b_{k}f_{k}^{\top}e^{-\lambda\tau}\Big{)}+K-\sum\limits_{k=1}^{m}b_{k}g_{k}^{\top}e^{-\lambda\tau}.$

For $j=1,2,\ldots,p$ and $k=1,2,\ldots,m$, define

$\xi_{jk}=\eta_{jk}+\frac{k}{m}\big{(}\mu_{j}-\eta_{jk}\big{)},\
\xi_{jm}=\mu_{j}.$ (21)

Let

$\displaystyle C_{1}=C,\
C_{k}=C-\sum\limits_{i=1}^{k-1}b_{i}f_{i}^{\top}e^{-\lambda\tau},$ (22)
$\displaystyle K_{1}=K,\
K_{k}=K-\sum\limits_{i=1}^{k-1}b_{i}g_{i}^{\top}e^{-\lambda\tau},$

where $k=2,3,\ldots,m$, then Problem 1 can be transformed into partial pole
assignment problems for $m$ single-input second-order linear systems. For
$k=1$, $f_{1}$ and $g_{1}$ can be obtained by Algorithm 1 such that the
eigenvalues $\left\\{{{\lambda_{i}}}\right\\}_{i=1}^{p}$ of the open-loop
pencil $P(\lambda)$ are reassigned to $\big{\\{}\xi_{j1}\big{\\}}_{j=1}^{p}$.
However, the system matrices $C_{2}$ and $K_{2}$ are no longer symmetric after
the first-step assignment. Therefore, Algorithm 1 cannot be applied for
subsequent assignment. For multi-input control systems, we propose the
following multi-step method to solve Problem 1. Suppose that after
$(k-1)$-step assignment, where $2\leq k<m$, the system

$M\ddot{x}(t)+C_{k}\dot{x}(t)+K_{k}x(t)=0$ (23)

has the eigenvalues $\big{\\{}\xi_{j,k-1}\big{\\}}_{j=1}^{p}$ and the
eigenpairs
$\left\\{{\left({{\lambda_{i}},{x_{i}}}\right)}\right\\}_{i=p+1}^{2n}$. For
the $k$-step, we need to find the feedback vectors $f_{k},\
g_{k}\in\mathbb{R}^{n}$, by single-input feedback control

$M\ddot{x}(t)+C_{k}\dot{x}(t)+K_{k}x(t)=b_{k}\left(f_{k}^{\top}\dot{x}(t)e^{-\lambda\tau}+g_{k}^{\top}x(t)e^{-\lambda\tau}\right),$

such that the eigenvalues $\big{\\{}\xi_{j,k-1}\big{\\}}_{j=1}^{p}$ of the
system (23) are reassigned to $\big{\\{}\xi_{j,k}\big{\\}}_{j=1}^{p}$ and the
remaining eigenstructure keeps the no spill-over property. After $m$-step
assignment, the feedback matrices $F$ and $G$ can be obtained. Then finding
the feedback vectors $f_{k},\ g_{k}\in\mathbb{R}^{n}$ can be expressed as the
following problem.

Problem 2. _Given $M$, $C$, $K$, $B$, $\Lambda_{1}$, $X_{1}$, $\tau$ and
$\Sigma_{1}$. For $k=1,2,\ldots,m$, let $\\{\xi_{jk}\\}_{j=1}^{p}$ and
$\left\\{C_{k},K_{k}\right\\}$ be defined by (21) and (22) respectively. Find
the two feedback vectors $f_{k}$ and $g_{k}$ in sequence such that the single-
input closed-loop delayed pencil_

$P_{\tau
k}(\lambda)=\lambda^{2}M+\lambda\left(C_{k}-b_{k}f_{k}^{\top}e^{-\lambda\tau}\right)+K_{k}-b_{k}g_{k}^{\top}e^{-\lambda\tau}$

_has the desired eigenvalues $\big{\\{}\xi_{jk}\big{\\}}_{j=1}^{p}$ and the
eigenpairs $\left\\{(\lambda_{i},x_{i})\right\\}_{i=p+1}^{2n}$._

######  Lemma 4.

[10] For $k=1,2,\ldots,m$, and arbitrary $\beta_{k}\in\mathbb{C}^{p}$, define

$f_{k}=MX_{1}\beta_{k},\
g_{k}=\left(MX_{1}\Lambda_{1}+CX_{1}\right)\beta_{k},$ (24)

then the single-input closed-loop delayed pencil $P_{\tau k}(\lambda)$ has the
desired eigenpairs $\left\\{(\lambda_{i},x_{i})\right\\}_{i=p+1}^{2n}$, i.e.,
the no spill-over property is preserved.

Let $\big{\\{}(\xi_{jk},y_{jk})\big{\\}}_{j=1}^{p}$ be the eigenpairs of the
$P_{\tau k}(\lambda)$, and define

$D_{k}={\rm{diag}}\big{(}\xi_{1k},\xi_{2k},\ldots,\xi_{pk}\big{)},\
Y_{k}=\big{[}y_{1k},y_{2k},\ldots,y_{pk}\big{]},$
$H_{k}=\left(h_{ls}^{(k)}\right)=X_{1}^{\top}MY_{k}D_{k}+\Lambda_{1}X_{1}^{\top}MY_{k}+X_{1}^{\top}CY_{k}.$
(25)

From Lemma 4, solving Problem 2 is transformed into determining vector
$\beta_{k}$ such that

$M{Y_{k}}{D_{k}^{2}}+C_{k}{Y_{k}}{D_{k}}-b_{k}f_{k}^{\top}{Y_{k}}{D_{k}}e^{-\tau
D_{k}}+K_{k}{Y_{k}}-bg_{k}^{\top}{Y_{k}}e^{-\tau D_{k}}=0.$ (26)

Substituting $f_{k},g_{k}$ defined in (24) into (26), and according to the
definition of $H_{k}$ in (25), we have

$\displaystyle M{Y_{k}}{D_{k}^{2}}+C_{k}{Y_{k}}{D_{k}}+K_{k}{Y_{k}}$
$\displaystyle=b_{k}\beta_{k}^{\top}(X_{1}^{\top}MY_{k}D_{k}+\Lambda_{1}X_{1}^{\top}MY_{k}+X_{1}^{\top}CY_{k})e^{-\tau
D_{k}}$ (27) $\displaystyle=b_{k}\beta_{k}^{\top}H_{k}e^{-\tau
D_{k}}:=b_{k}\gamma_{k},$

where $\gamma_{k}=\beta_{k}^{\top}H_{k}e^{-\tau D_{k}}$. Similarly, choose
$\gamma_{k}=[1,1,\ldots,1]\in\mathbb{R}^{p}$, then

$\beta_{k}^{\top}H_{k}=[1,1,\ldots,1]e^{\tau D_{k}}.$ (28)

From (27), we can solve the linear systems

$\left(\xi_{jk}^{2}M+\xi_{jk}C_{k}+K_{k}\right)y_{jk}=b_{k},\ j=1,2,\ldots,p$
(29)

to get $Y_{k}$ by choosing the appropriate parameters $\\{\eta_{jk}\\}$ such
that the coefficient matrix of linear systems (29) are nonsingular. Then the
matrix $H_{k}$ can be formed from (25), and $\beta_{k}$ in (24) can be
obtained by solving the linear system (28).

Clearly, the method mentioned earlier necessitates the solution of at least
$((m-1)\cdot p)$ $n$-order linear systems. When dealing with a second-order
system with a large degree of freedom, the computational expenses can be quite
substantial. However, in practical engineering scenarios, the requirement to
reassign poles is usually limited, with $p\ll n$ as a general rule. To
minimize computational costs, we establish a new connection among system
matrices, undesired eigenvalues and their corresponding eigenvectors, desired
eigenvalues, and control vectors. Subsequently, we develop an efficient
algorithm for forming matrix $H_{k}$ without the need to calculate $Y_{k}$.

Based on the definition of $H_{k}$ in (25), we can derive

$\displaystyle h_{ls}^{(k)}$
$\displaystyle=x_{l}^{\top}\left[\xi_{sk}M+\lambda_{l}M+C\right]y_{sk}$
$\displaystyle=\frac{x_{l}^{\top}}{\xi_{sk}-\lambda_{l}}\left[\xi_{sk}^{2}M+\xi_{sk}C-\Big{(}\lambda_{l}^{2}M+\lambda_{l}C\Big{)}\right]y_{sk}$
$\displaystyle=\frac{x_{l}^{\top}}{\xi_{sk}-\lambda_{l}}\Bigg{(}\xi_{sk}^{2}M+\xi_{sk}\Big{(}C-\sum\limits_{i=1}^{k-1}b_{i}f_{i}^{\top}e^{-\tau
D_{k}}\Big{)}+\Big{(}K-\sum\limits_{i=1}^{k-1}b_{i}g_{i}^{\top}e^{-\tau
D_{k}}\Big{)}$ $\displaystyle\ \ \ \ \ \
-\Big{(}\lambda_{l}^{2}M+\lambda_{l}C+K\Big{)}+\xi_{sk}\sum\limits_{i=1}^{k-1}b_{i}f_{i}^{\top}e^{-\tau
D_{k}}+\sum\limits_{i=1}^{k-1}b_{i}g_{i}^{\top}e^{-\tau D_{k}}\Bigg{)}y_{sk}$
$\displaystyle=\frac{x_{l}^{\top}}{\xi_{sk}-\lambda_{l}}\Bigg{(}\Big{(}\xi_{sk}^{2}M+\xi_{sk}C_{k}+K_{k}\Big{)}-\Big{(}\lambda_{l}^{2}M+\lambda_{l}C+K\Big{)}+\sum\limits_{i=1}^{k-1}b_{i}\Big{(}\xi_{sk}f_{i}^{\top}+g_{i}^{\top}\Big{)}e^{-\tau
D_{k}}\Bigg{)}y_{sk}.$

According to $\left(\lambda_{l}^{2}M+\lambda_{l}C+K\right)x_{l}=0$ and (29),
we have

$h_{ls}^{(k)}=\frac{x_{l}^{\top}b_{k}}{\xi_{sk}-\lambda_{l}}+\frac{e^{-\tau\xi_{sk}}x_{l}^{\top}\left(\sum\limits_{i=1}^{k-1}b_{i}\left(\xi_{sk}f_{i}^{\top}+g_{i}^{\top}\right)\right)y_{sk}}{\xi_{sk}-\lambda_{l}}.$
(30)

Let

$G_{k}=X_{1}^{\top}\sum\limits_{i=1}^{k-1}b_{i}\beta_{i}^{\top},\
W_{k}=\left(w_{ls}^{(k)}\right)=X_{1}^{\top}\sum\limits_{i=1}^{k-1}b_{i}\beta_{i}^{\top}H_{k}=G_{k}H_{k}.$

Substituting $H_{k}$ define in (25) into $W_{k}$, we can obtain

$\displaystyle w_{ls}^{(k)}$
$\displaystyle=x_{l}^{\top}\Bigg{(}\sum\limits_{i=1}^{k-1}{b_{i}\beta_{i}^{\top}}\Big{(}\xi_{sk}X_{1}^{\top}M+\Lambda_{1}X_{1}^{\top}M+X_{1}^{\top}C\Big{)}\Bigg{)}y_{sk}$
(31)
$\displaystyle=x_{l}^{\top}\Bigg{(}\sum\limits_{i=1}^{k-1}b_{i}\Big{(}\xi_{sk}f_{i}^{\top}+g_{i}^{\top}\Big{)}\Bigg{)}y_{sk}.$

######  Remark 3.

From (30) and (31), we find that each element of $W_{k}$ has a strong
correlation with the corresponding element of $H_{k}$. We can use this
relationship to derive a low order matrix equation about $H_{k}$.

Let

$V_{k}=\left({\begin{array}[]{*{20}{c}}\frac{1}{\xi_{1k}-\lambda_{1}}&\ldots&\frac{1}{\xi_{pk}-\lambda_{1}}\\\
\vdots&\ddots&\vdots\\\
\frac{1}{\xi_{1k}-\lambda_{p}}&\ldots&\frac{1}{\xi_{pk}-\lambda_{p}}\end{array}}\right),\
$ $A_{k}={\rm{diag}}\left(x_{1}^{\top}b_{k},\ldots,x_{p}^{\top}b_{k}\right),\
T_{k}={\rm{diag}}\left(e^{-\tau\xi_{1k}},\ldots,e^{-\tau\xi_{pk}}\right),\
R_{k}=V_{k}T_{k}.$

By (30) and (31), $H_{k}$ satisfies the matrix equation described by

$H_{k}=U_{k}+(V_{k}T_{k})\ast(G_{k}H_{k})=U_{k}+R_{k}\ast W_{k},$ (32)

where
$U_{k}=\left(u_{ls}^{(k)}\right)=\left(\frac{x_{l}^{T}b_{k}}{\xi_{sk}-\lambda_{l}}\right)=A_{k}V_{k}$
and $\ast$ represents the Hadamard product.

Let $A=\big{[}a_{1},a_{2},\ldots,a_{n}\big{]}$ be an $m\times n$ matrix,
$a_{i}$ denote the $i$-th column of the matrix $A$, the $mn$ dimension vector
${\rm{vec}}(A)=\Big{[}a_{1}^{\top}$,
$a_{2}^{\top},\ldots,a_{n}^{\top}\Big{]}^{\top}$ be called the column
straightening of matrix $A$, $A\otimes B$ represent the Kronecker product of
matrix $A$ and $B$, and $I_{n}$ represent the $n$-order identity matrix. Then
the column straightening of the matrix with the Hadamard product and Kronecker
product of the matrix has the following properties.

######  Lemma 5.

[19] Let $A$ be an $m\times n$ matrix.
(1) If $B$ is an $m\times n$ matrix, then ${\rm{vec}}\left(A\ast
B\right)={\rm{diag}}\left({\rm{vec}}(A)\right){\rm{vec}}(B)$;
(2) If $B$ and $C$ are $n\times p$ and $p\times q$ matrix, respectively, then
${\rm{vec}}(ABC)=(C^{\top}\otimes A){\rm{vec}}(B)$.

From Lemma 5, the matrix equation (32) can be transformed into the following
$p^{2}$-order linear system

$\big{[}I_{p^{2}}-{\rm{diag}}\left({\rm{vec}}(R_{k})\right)(I_{p}\otimes
G_{k})\big{]}{\rm{vec}}(H_{k})={\rm{vec}}(U_{k}).$ (33)

Let $Z_{k}=I_{p^{2}}-{\rm{diag}}\left({\rm{vec}}(R_{k})\right)(I_{p}\otimes
G_{k})$, because $R_{k}$, $G_{k}$ and $U_{k}$ are all known, the matrix
$H_{k}$ can be obtained by solving the $p^{2}$-order linear system (33), and
the $\beta_{k}$ can be obtained by solving the $p$-order linear system (28).
In summary, we can derive the following theorem.

######  Theorem 2.

For $k=1,2,\ldots m$, if the single-input control system
$\left(M,C_{k},K_{k},b_{k}\right)$ is partially controllable with respect to
the $\big{\\{}\xi_{j,k}\big{\\}}_{j=1}^{p}$,
$\left\\{{{\lambda_{i}}}\right\\}_{i=1}^{p}$ and
$\big{\\{}\xi_{jk}\big{\\}}_{j=1}^{p}$ are all distinct,
$\big{\\{}\xi_{jk}\big{\\}}_{j=1}^{p}\cap\left\\{\lambda_{i}\right\\}_{i=1}^{2n}=\emptyset,\
\left\\{\lambda_{i}\right\\}_{i=1}^{p}\cap\left\\{\lambda_{i}\right\\}_{i=p+1}^{2n}=\emptyset$,
and $\big{\\{}y_{jk}\big{\\}}_{j=1}^{p}$ are the solutions of (29), then
Problem 2 has a solution, which can be expressed by (24), where $\beta_{k}$ is
the solution of linear system (28).

Based on the Theorem 1 and Theorem 2, the calculation process of solving the
multi-input partial quadratic pole assignment problem with time delay can be
summarized as the following algorithm.

Algorithm 2 A multi-step method for Problem 1 by multi-input control.
---
Input:
The symmetric matrices $M,C\in\mathbb{R}^{n\times n}$ with $M$ positive
definite;
The full column rank control matrix $B\in{\mathbb{R}^{n\times m}}$ and the
time delay $\tau>0$;
The self-conjugate eigenpairs $\left\\{(\lambda_{i},x_{i})\right\\}_{i=1}^{p}$
and a self-conjugate set $\\{{{\mu_{i}}}\\}_{i=1}^{p}$.
Output:
State feedback real matrices $F$ and $G$.
1: Form
$\Lambda_{1}={\rm{diag}}\big{(}\lambda_{1},\lambda_{2},\ldots,\lambda_{p}\big{)}$
and $X_{1}=\big{[}x_{1},x_{2},\ldots,x_{p}\big{]}$;
2: Choose $\eta_{jk}$ and compute
$\xi_{jk}=\eta_{jk}+\frac{k}{m}\big{(}\mu_{j}-\eta_{jk}\big{)}$,
$j=1,2,\ldots,p$, $k=1,2,\ldots,m$;
3: Compute $f_{1}=MX_{1}\beta_{1}$,
$g_{1}=\big{(}MX_{1}\Lambda_{1}+CX_{1}\big{)}\beta_{1}$ by Algorithm 1;
4: For $k=2,3,\ldots,m$, do
4.1: Compute $R_{k},G_{k},U_{k}$. If ${\rm{cond}}\left(Z_{k}\right)$ is large,
take another $\eta_{jk}$;
4.2: Compute $H_{k}$ by solving the linear system (33);
4.3: Compute $\beta_{k}$ by solving the linear system (28);
4.4: Compute $f_{k}=MX_{1}\beta_{k}$,
$g_{k}=\left(MX_{1}\Lambda_{1}+CX_{1}\right)\beta_{k}$;
5: Form $F=\big{[}f_{1},f_{2},\ldots,f_{m}\big{]}$,
$G=\big{[}g_{1},g_{2},\ldots,g_{m}\big{]}$.

##  4  Numerical Examples

In this section, we provide three examples to illustrate the effectiveness of
Algorithm 1 and Algorithm 2. All the numerical examples are implemented in
MATLAB R2020a and run on the PC with 3.80 GHz Inter Core i7, 10700K CPU. We
use

${\rm{Error_{1}}}=\big{\|}MY_{1}\Sigma_{1}^{2}+CY_{1}\Sigma_{1}-BF^{\top}Y_{1}\Sigma_{1}{\rm{e}}^{-\tau\Sigma_{1}}+KY_{1}-BG^{\top}Y_{1}{\rm{e}}^{-\tau\Sigma_{1}}\big{\|}_{F}$

and

${\rm{Error_{2}}}=\big{\|}M{X_{2}}\Lambda_{2}^{2}+C{X_{2}}{\Lambda_{2}}-BF^{\top}{X_{2}}{\Lambda_{2}}{\rm{e}}^{-\tau\Lambda_{2}}+K{X_{2}}-BG^{\top}{X_{2}}{\rm{e}}^{-\tau\Lambda_{2}}\big{\|}_{F}$

to measure the residuals of the closed-loop system. Example 1 and Example 2
show the correctness of Algorithm 2, and Example 3 shows Algorithm 2 is more
efficient than the traditional multi-step method in [17] in the case $p\ll n$.

Example 1. [17] Consider the second-order control system

$M=I_{3},\ C=\left({\begin{array}[]{*{20}{c}}2.5&2&0\\\ 2&1.7&0.4\\\
0&0.4&2.5\end{array}}\right),\ K=\left({\begin{array}[]{*{20}{c}}16&12&0\\\
12&13&4\\\ 0&4&29\end{array}}\right).$

Time delay $\tau=0.1$ and
$B=b=\big{(}{\begin{array}[]{*{20}{c}}1&3&3\end{array}}\big{)}^{\top}$. The
corresponding open-loop pencil has 6 eigenvalues: $\lambda_{1,2}=-0.0129\pm
1.4389i$, $\lambda_{3,4}=-1.3342\pm 5.2311i$, $\lambda_{5,6}=-2.0030\pm
4.7437i$. In order to make the system more stable, the first two eigenvalues
$\lambda_{1,2}=-0.0129\pm 1.4389i$ are reassigned to $\mu_{1}=-0.2$ and
$\mu_{2}=-0.3$, and the remaining eigenvalues of the original system are kept
unchanged. Using Algorithm 1, we can obtain $\beta_{1}=(-0.3023+0.4678i,\
-0.3023-0.4678i)^{\top},$ the feedback vectors

$F=f=\left({\begin{array}[]{*{20}{c}}0.1428\\\ -0.1541\\\
0.0215\end{array}}\right),\ G=g=\left({\begin{array}[]{*{20}{c}}-0.9698\\\
1.2224\\\ -0.1852\end{array}}\right),$

and

${\rm{Error_{1}}}=6.0497{\rm{e}}-15,\ {\rm{Error_{2}}}=1.9486{\rm{e}}-13.$

Example 2. Consider the same system matrices in Example 1 with time delay
$\tau=0.1$ and control matrix $B=\left({\begin{array}[]{*{20}{c}}1&2\\\ 3&2\\\
3&4\end{array}}\right).$ The first two eigenvalues $\lambda_{1,2}=-0.0129\pm
1.4389i$ are reassigned to $\mu_{1}=-0.2$ and $\mu_{2}=-0.3$, and the
remaining eigenvalues of the original system are kept unchanged. Let
$\eta_{jk}=\lambda_{j},j=1,2,\ldots,p$. Applying Algorithm 2, we can obtain
$\beta_{1}=(-0.3779+0.4117i,\ -0.3779-0.4117i)^{\top}$,
$\beta_{2}=(-0.4108-0.3047i,\ -0.4108+0.3047i)^{\top}$, the feedback matrices

$F=\left({\begin{array}[]{*{20}{c}}{0.0220}&{-0.6561}\\\ {-0.0131}&{0.7658}\\\
{0.0005}&{-0.1141}\end{array}}\right),\
G=\left({\begin{array}[]{*{20}{c}}{-1.0119}&{-0.2284}\\\ {1.2347}&{0.0669}\\\
{-0.1844}&{0.0047}\end{array}}\right),$

and

${\rm{Error_{1}}}=1.5638{\rm{e}}-12,\ {\rm{Error_{2}}}=2.0668{\rm{e}}-13.$

Example 3. Consider a mass-damp-spring system with $n$ degrees of freedom
shown as in Figure 1. The system matrices are
$M={\rm{diag}}\big{(}m_{1},m_{2},\ldots,m_{n}\big{)},$

Figure 1: Series mass-damping-spring system.

$C=\left({\begin{array}[]{*{20}{c}}{{c_{1}}+{c_{2}}}&{-{c_{2}}}&{}\hfil&{}\hfil\\\
{-{c_{2}}}&{{c_{2}}+{c_{3}}}&{-{c_{3}}}&{}\hfil\\\
{}\hfil&\ddots&\ddots&{}\hfil\\\
{}\hfil&{}\hfil&{-{c_{n}}}&{{c_{n}}}\end{array}}\right),\
K=\left({\begin{array}[]{*{20}{c}}{{k_{1}}+{k_{2}}}&{-{k_{2}}}&{}\hfil&{}\hfil\\\
{-{k_{2}}}&{{k_{2}}+{k_{3}}}&{-{k_{3}}}&{}\hfil\\\
{}\hfil&\ddots&\ddots&{}\hfil\\\
{}\hfil&{}\hfil&{-{k_{n}}}&{{k_{n}}}\end{array}}\right).$

Let $M=I_{n},c_{1}=k_{1}=0,c_{i}=8,k_{i}=150,i=2,3,\ldots,n$, time delay
$\tau=0.1$ and control matrix $B=\big{[}e_{1},e_{2}\big{]}$, where $e_{1}$ and
$e_{2}$ represent the first and second columns of matrix $I_{n}$,
respectively. Let the degrees of freedom of the system be 500, 1000, 2000,
3000, 4000 and 5000. In each of the six cases, only one eigenvalue is
unstable, and they are $\lambda_{969}=7.8049{\rm{e}}-14$,
$\lambda_{1993}=6.4293{\rm{e}}-13$, $\lambda_{3997}=1.3911{\rm{e}}-12$,
$\lambda_{5999}=1.5965e-12$, $\lambda_{7999}=1.9989{\rm{e}}-07$ and
$\lambda_{9999}=1.6973{\rm{e}}-07$, respectively. These eigenvalues are all
reassigned to $\mu_{1}=-0.2$. Let $\eta_{jk}=\lambda_{j},j=1,2,\ldots,p$, the
numerical results are shown in Table 1.

${\rm{n}}$ | ${\rm{CPU\ Time(s)}}$ | ${\rm{Error_{1}}}$ | ${\rm{Error_{2}}}$
---|---|---|---
Alg. 2 | Alg. [17] | Alg. 2 | Alg. [17] | Alg. 2 | Alg. [17]
500 | 0.0018 | 0.0095 | 1.8677e-13 | 1.8947e-13 | 4.5030e-09 | 4.5030e-09
1000 | 0.0029 | 0.0324 | 3.2900e-12 | 1.8293e-13 | 6.3745e-09 | 6.3745e-09
2000 | 0.0081 | 0.1677 | 2.5098e-12 | 1.9489e-13 | 1.0236e-08 | 1.0236e-08
3000 | 0.0252 | 0.3583 | 5.7325e-12 | 1.8936e-13 | 1.2699e-08 | 1.2699e-08
4000 | 0.0291 | 0.6484 | 2.5455e-12 | 1.9244e-13 | 1.4229e-08 | 1.4229e-08
5000 | 0.0415 | 1.0438 | 3.2718e-12 | 1.8946e-13 | 1.6358e-08 | 1.6358e-08
Table 1: Example 3 numerical results

Algorithm 2 shows that the calculations related to the degree of freedom $n$
are all the multiplication of matrices and vectors, and do not involve solving
$n$-order linear systems. Specifically, we only need to solve the $p$-order
linear system (28) and the $p^{2}$-order linear system (33). Therefore, the
time consumption of Algorithm 2 is much less than that of Algorithm in [17],
and the results in Table 1 are consistent with the theoretical prediction.
Moreover, as the degree of freedom of the system increases, the time
consumption of Algorithm [17] increases markedly, while the time consumption
of Algorithm 2 does not increase much.

##  5  Conclusion

In this paper, the partial pole assignment problem in symmetric quadratic
pencil with time delay is considered. We present a simple explicit solution
for this problem for the single-input system, which involves only the
multiplication of matrices and vectors. For the multi-input system, by
establishing a new matrix equality relation, we develop a novel multi-step
method to transform this problem into solving linear systems with low order.
Numerical examples show that the proposed method is effective, and both the
computational time and cost of the method proposed in this paper are markedly
reduced than the traditional multi-step method in the case $p\ll n$. Our
method is particularly well-suited for the large-scale system where only a
small part of the spectrum needs to be reassigned.

## Declaration of Competing Interest

The authors declare that they have no known competing financial interests or
personal relationships that could have appeared to influence the work reported
in this paper.

## Data availability

Data will be made available on request.

## Acknowledgments

The author sincerely thanks Professor Hua Dai for the careful guidance on the
partial pole assignment in symmetric quadratic pencil.

## References

## References

  * [1] B.N. Datta, D.R. Sarkissian, Theory and computations of some inverse eigenvalue problems for the quadratic pencil, Contemp. Math. 280 (2001) 221-240.
  * [2] W.W. Lin, J.N. Wang, Partial pole assignment for the quadratic pencil by output feedback control with feedback designs, Numer. Linear Algebra Appl. 12 (2005) 967-979.
  * [3] S. Xu, J. Qian, Orthogonal basis selection method for robust partial eigenvalue assignment problem in second-order control system, J. Sound Vib. 317 (2008) 1-19.
  * [4] T. Li, E.K. Chu, Pole assignment for linear and quadratic systems with time-delay in control, Numer. Linear Algebra Appl. 20 (2013) 291-301.
  * [5] A.J. Laub, W.F. Arnold, Controllability and observability criteria for multivariate linear second order models, IEEE Trans. Autom. Control. 29 (1984) 163-165.
  * [6] B.N. Datta, S.Elhay, Y.M. Ram, Orthogonality and partial pole assignment for the symmetric definite quadratic pencil, Linear Algebra Appl. 257 (1997) 29-48.
  * [7] Y.M. Ram, S. Elhay, Pole assignment in vibratory systems by multi-input control, J. Sound Vib. 230 (2000) 309-321.
  * [8] Y.M. Ram, J.E. Mottershead, The receptance method in active vibration control, AIAA J. 45 (2007) 562-567.
  * [9] Y.M. Ram, J.E. Mottershead, M.G. Tehrani, Partial pole placement with time delay in structures using the receptance and the system matrices, Linear Algebra Appl. 434 (2011) 1689-1696.
  * [10] Z.J. Bai, M.X. Chen, J.K. Yang, A multi-step hybrid method for multi-input partial quadratic eigenvalue assignment with time delay, Linear Algebra Appl. 437 (2012) 1658-1669.
  * [11] Z.J. Bai, M. Lu, Q.Y. Wan, Minimum norm partial quadratic eigenvalue assignment for vibrating structures using receptances and system matrices, Mech. Syst. Signal Process. 112 (2018) 265-279.
  * [12] Y.M. Ram, J.E. Mottershead, Multiple-input active vibration control by partial pole placement using the method of receptance, Mech. Syst. Signal Process. 40 (2013) 727-735.
  * [13] M. Chen, H. Xie, A receptance method for partial quadratic pole assignment of asymmetric systems, Mech. Syst. Signal Process. 165 (2022) 108348.
  * [14] D. Richiedei, I. Tamellin, A. Trevisani, Pole-zero assignment by the receptance method: multi-input active vibration control, Mech. Syst. Signal Process. 172 (2022) 108976.
  * [15] J.E. Mottershead, M.G. Tehrani,Y.M. Ram, Assignment of eigenvalue sensitivities from receptance measurements, Mech. Syst. Signal Process. 23 (2009) 1931-1939.
  * [16] X.B. Mao, Spectral Modification Problems in Structural Dynamics, Ph.D Thesis, Nanjing University of Aeronautics and Astronautics, 2011.
  * [17] H. Liu, Y. Yuan, A multi-step method for partial quadratic pole assignment problem with time delay, Appl. Math. Comput. 283 (2016) 29-35.
  * [18] X.R. Meng, X.P. Yue, On the inverse problem of a class of Cauchy type matrix, Syst. Sci. Comput. 32 (2011) 1690-1697.
  * [19] X.D. Zhang, Matrix Analysis and Applications, Tsinghua University Press, 2004.