# Marine$\mathcal{X}$: Design and Implementation of Unmanned Surface Vessel
for Vision Guided Navigation

Muhayy Ud Din, Ahmed Humais, Waseem Akram, Mohamed Alblooshi , Lyes Saad
Saoud,
Abdelrahman Alblooshi, Lakmal Seneviratne, and Irfan Hussain∗ Khalifa
University Center for Autonomous Robotic Systems (KUCARS), Khalifa University,
United Arab Emirates.∗ Corresponding Author, Email<EMAIL_ADDRESS>
###### Abstract

Marine robots, particularly Unmanned Surface Vessels (USVs), have gained
considerable attention for their diverse applications in maritime tasks,
including search and rescue, environmental monitoring, and maritime security.
This paper presents the design and implementation of a USV named
marine$\mathcal{X}$. The hardware components of marine$\mathcal{X}$ are
meticulously developed to ensure robustness, efficiency, and adaptability to
varying environmental conditions. Furthermore, the integration of a vision-
based object tracking algorithm empowers marine$\mathcal{X}$ to autonomously
track and monitor specific objects on the water surface. The control system
utilizes PID control, enabling precise navigation of marine$\mathcal{X}$ while
maintaining a desired course and distance to the target object. To assess the
performance of marine$\mathcal{X}$, comprehensive testing is conducted,
encompassing simulation, trials in the marine pool, and real-world tests in
the open sea. The successful outcomes of these tests demonstrate the USV’s
capabilities in achieving real-time object tracking, showcasing its potential
for various applications in maritime operations.

###### Index Terms:

Autonomous navigation, marine robotics, autonomous systems.

##  I Introduction

Marine robotics emerging as a significant field to explore and understand the
complex marine ecosystem. There are two main classes of marine robots that are
underwater vehicles and surface vehicles. The underwater vehicles are mainly
used for underwater resource exploration, inspection, studying marine life,
and for the collection of crucial data to study climate change. The surface
vehicles, such as Unmanned surface vessels (USVs) are playing a significant
role to enhance the maritime security [1], perform the search and rescue
operations [2], environmental monitoring [3], and for disaster response [4].
The use of USVs in these areas enhances efficiency and minimizes the risks to
human life.

Unmanned surface vehicles are complex in design as they required consistent
coordination among their mechanical components, sensors, actuators, and
navigation algorithms to effectively carry out their designated tasks. The
mechanical configuration of a USV is identical to a conventional vessel,
however, smaller in size [5]. There are various types of vessel design among
them, mono-hull design and catamaran (dual hull) design are most commonly used
[6]. The catamaran design provides enhanced stability and payload capacity
compared to mono hull designs, which makes it a popular choice for the
designing of testing platforms in the research field [7] [8]. Despite the
mechanical design, it is also required to build the Guidance, Navigation, and
Control system [9]. Furthermore, path planning, collision avoidance [10] and
path following [11] are essential for USV to perform the navigation task
autonomously.

Figure 1: Marine$\mathcal{X}$ operating in different environments. a)
represents Gazebo simulation, b) represents real sea experiment, c) shows the
experiment in the marine pool, and d) shows the output of marine$\mathcal{X}$
onboard camera image after applying the object detection algorithm.

In recent years, several USVs are developed by the research community. These
systems are designed by keeping in mind the specific application to be
performed. For instance, SESAMO [12] is developed with the catamaran design
for the sampling of sea-surface microlayer. ROAV [13] is a USV, designed for
river applications, with the capability of carrying up to a 50kg payload. In
order to demonstrate autonomous navigation capabilities, ARTMEMIS [14] was
developed by MIT. Several commercial USVs are also developed by robotic
companies, such as, Wave Glider [15], it is a mono-hull design USV developed
by Liquid Robotics Inc (https://www.liquid-robotics.com/). Otter is a
catamaran design developed by Maritime Robotics
(https://www.maritimerobotics.com/otter). The commercial USVs are well
equipped with functionalities However, they are very expensive. This leads us
to the motivation of developing our own USV for particular tracking
applications.

Several control algorithms such as Proportional Integral Derivative (PID)
control, Model predictive control, and neural network-based control are
proposed to navigate the USV autonomously [16]. In order to estimate the
position of the USV, all these control algorithms required localization
strategies such as GPS-based localization. Visual servo control provides real-
time visual feedback to guide the motion and control of a robot, enabling
precise and dynamic interactions with the environment based on visual
information. It does not require explicit localization and it is widely
applied in tasks such as object tracking and autonomous navigation [17].

This study presents the design and fabrication of unmanned surface vessels.
Moreover, a vision-guided navigation algorithm is developed that autonomously
navigates marine$\mathcal{X}$ toward the given target.

Contributions: This work makes significant contributions in the following
aspects:

  * •

Design and Development: We successfully designed and developed the unmanned
surface vessel, marine$\mathcal{X}$, using the robust catamaran design. This
choice ensures adaptability to diverse environmental conditions, making it
ideal for various maritime tasks.

  * •

Vision-Based Feedback Control: The implementation of a vision-based feedback
control system using PID control allows precise visual servoing and efficient
object tracking on the water surface.

  * •

Comprehensive Testing: Extensive testing, including simulations, indoor marine
pool evaluations, and real-world open sea scenarios, validates
marine$\mathcal{X}$’s design and autonomous navigation algorithm. The results
highlight its capabilities for diverse maritime operations.

Figure 2: Schematic of sensors, actuators, and electronic components of the
marine$\mathcal{X}$

##  II Hardware design

The hardware design plays a key role in the vessel’s reliability and
performance. A well-engineered hardware design ensures the USV’s stability,
buoyancy, and hydrodynamic efficiency, enabling smooth and efficient
navigation in various marine conditions. This section will explain the
marine$\mathcal{X}$ design process and core hardware components such as
sensors, actuators, computing units, CAD models, and fabrication process.

Figure 3: Design and fabrication process of marine$\mathcal{X}$. a) and b)
depict the complete CAD design and the shredded view of the components,
respectively. c) shows the stress test analysis. d) shows the first buoyancy
test of marine$\mathcal{X}$

###  II-A Electronic components

The main components of the Marine$\mathcal{X}$ are shown in Fig 2. The
actuation system consists of two T200 thrusters by Blue Robotics Inc
(https://bluerobotics.com/). The thrusters include both clockwise and
counterclockwise propellers. The propeller’s maximum rotational speed is 4000
rpm and it can produce up to 5.05 kgf thrust. The rpm are controlled using the
electronic speed controller (ESC) to ensure the smooth and precise control.
The control inputs for autonomous navigation is computed using Navio2 board by
HiPi Industries Inc (https://navio2.hipi.io/). It is an autopilot header for
Raspberry Pi4, it also contains the onboard IMU and GPS sensors. The Navio2
with the integration of Raspberry Pi4, control the actuators for autonomous
navigation. The USV incorporates the powerful NVIDIA Jetson TX2 computing
board. It is responsible for processing advance computer vision algorithms.
This module empowers the USV to run the state-of-the-art vision algorithms for
accurate object detection tasks on the video stream received from the ZED Mini
camera mounted at the front of the USV enclosure. In order to operate the
marine$\mathcal{X}$ in a teleportation mode, an RC control and receiver is
used developed by Fataba (https://www.futaba.com/). The RC receiver is
connected to the Raspberry Pi that receive the command from RC control and
forward it to the thrusters. To sustain the Marin$\mathcal{X}$ operations, a
high-capacity 10000mAh LiPo Battery is employed. Fig 2 provides a visual
representation of the electronic components and connection flow made for the
USV.

###  II-B CAD Model and Fabrication

We choose catamaran design as it evident batter stability over the single hull
design for autonomous vessels. The CAD model for the marine$\mathcal{X}$ is
shown in Fig. 3-a and the exploded view of the components is shown in Fig 3-b.
The weight of the the marine$\mathcal{X}$ is 25 kg and it can move with the
speed of up-to 4 knots. The hulls are 3D printed and painted with white and
blue color. From inside, the hulls are filled with the bouncy foam to provide
the batter payload capacity. It can carry payload of up-to 20 kilogram. An
aluminium frame is designed using Bosch profiles, it is connected with the
hulls via acrylic sheet. Thrusters are also connected with hulls using acrylic
sheet, A water tightening enclosure is used to carry all the electronic
components such as raspberry pi, TX2, camera and LiPo battery. This enclosure
is connected with the frame using acrylic sheet.

##  III Software architecture

The software architecture of the marine$\mathcal{X}$ is shown in Fig. 4. The
main software system resides in Raspberry Pi, it consists of USV Firmware that
provides sensors and actuators interface for the high-level application. The
vision-related applications are running on the TX2 that has onboard NVIDIA GPU
for fast processing.

###  III-A USV Firmware

USV firmware is a C++ based software application, developed on top of Resbian
operating system which is a Linux-based default OS for Raspberry Pi. The
communication layer consists of ROS Noetic, it is used to communicate among
different hardware components such as sensors are actuators. The USV Firmware
module contains the low-level ROS driver to communicate with Sensors (such as
GPS and IMU), actuators (such as thrusters), and provide ros-topics to send
and receive data from sensors and actuators. Moreover, USV Firmware is also
responsible to receive the commands from the remote control and forward them
to thrusters for teleportation. The high-level application will consist of a
navigation algorithm. Any feasible control scheme and navigation algorithm can
be implemented as a ROS node in a high-level application module.

Figure 4: Overview of software architecture of marine$\mathcal{X}$ Figure 5:
Snapshots of marine$\mathcal{X}$’s in Gazebo simulation. a1-3) show
marine$\mathcal{X}$ in different navigation scenes. a4) shows the
marine$\mathcal{X}$ camera image after applying the detection algorithm,

###  III-B ROS-based Gazebo Simulation

Gazebo is a powerful and widely used open-source robotics simulation software.
It enables the realistic emulation of various environmental conditions and
vessel dynamics. By creating a virtual environment, we can test and refine
control strategies and navigation systems in a safe way. Gazebo simulation
model for marine$\mathcal{X}$ is created using a Unified robotic description
format (URDF). The hydrodynamic and hydrostatic parameters of
marine$\mathcal{X}$ are estimated using ANSYS simulator
(https://www.ansys.com).

In order to test the navigation algorithms, we used gazebo based open-source
marine simulator (https://github.com/osrf/mbzirc.git) developed by Open
Robotics for the MBZIRC Maritime Grand Challenge. It is developed in C++ and
Python. It uses ROS2 Galactic for communication among modules. Fig 5 shows
snapshots of the marine$\mathcal{X}$ simulation in MBZIRC simulator. The
simulation helps in identifying potential issues and improve overall system
robustness. It serves as a crucial bridge between theoretical concepts and
real-world implementations, ensuring that marine$\mathcal{X}$ can operate
effectively and autonomously in diverse maritime applications. The
marine$\mathcal{X}$ simulation model could also easily be incorporate with
Nav2 (https://navigation.ros.org/). It is a ROS2-based navigation stack that
provides several ready to used path planners for navigation.

##  IV Vision Guided Navigation

Vision-guided navigation consists of applying advanced computer vision
techniques to detect the target object and using the control strategies that
navigate the USV in a way that it follows (or navigates towards) the detected
object. It is an ideal solution for the tasks such as maritime surveillance,
environmental monitoring, search and rescue missions, and offshore
infrastructure inspection. Fig. 7 shows the framework for vision-guided
navigation that is implemented on marine$\mathcal{X}$. The raw images captured
by the marine$\mathcal{X}^{\prime}s$ camera are passed to the object detector,
SEC.IV-A explains the vision pipeline for object detection. Based on the
detection output, distance and heading error will be computed (details in Sec.
IV-B). The control law will compute the appropriate control signal that will
be used to generate the required thrust.

Figure 6: Screenshots of the vessels used to generate the training dataset.
Fig-a, show the 3D-printed vessels used for real experiments. Fig-b shows the
vessels in the simulation used for gazebo experiments.

###  IV-A Vision Pipeline

For object detection, deep learning models are considered highly effective.
various deep learning-based object detectors are proposed such as [18, 19,
20]. This work used Yolov5 [21] model for object detection. It is very
effective and commonly used for object detection. For real scenario, the model
is applied on custom dataset with 3 different 3D printed vessels, shown in
Fig.6-a. For simulation, the model is trained on the gazebo models of the
vessels as shown in Fig. 6-b, The dataset is recorded by putting the vessels
into the marine pool and record the vessels’ images using
marine$\mathcal{X}$’s onboard camera.

YOLOv5 is a popular deep learning object detection model developed by
Ultralytics [21]. It is built using PyTorch (https://pytorch.org/), a popular
deep learning framework, and it follows a one-stage object detection approach,
which means it directly predicts bounding boxes and class probabilities for
multiple objects in a single forward pass through the neural network. This
allows YOLOv5 to achieve faster inference times compared to two-stage object
detection models.

Figure 7: Framework for marine$\mathcal{X}$’s vision guided navigation.

The fundamental structure of YOLOv5 relies on a backbone network, often a
Convolutional Neural Network (CNN), responsible for extracting essential
features from the input image. These extracted features then undergo several
subsequent layers, including convolutional, upsampling, and fusion layers, to
produce detailed and high-resolution feature maps. In YOLOv5, feature
aggregation is enhanced by incorporating the PAN (Path Aggregation Network).
This addition allows the model to gather features from various levels of the
network, enabling it to effectively capture information at different scales
for improved object detection. During the detection process, YOLOv5 follows
distinct phases. It performs box and class predictions while also leveraging
features from the network’s head. By integrating these features from the head,
the model can make more precise and comprehensive predictions for object
bounding boxes and their corresponding classes. To effectively train the
YOLOv5 model, a substantial dataset with labeled examples, including bounding
box annotations for the objects of interest, is necessary. The model’s
training process involves utilizing techniques like backpropagation and
gradient descent to iteratively adjust the network parameters and enhance
object detection performance. YOLOv5 provides multiple model sizes, such as
YOLOv5s, YOLOv5m, YOLOv5l, and YOLOv5x, each varying in depth and
computational complexity. These diverse variants offer a balance between
inference speed and detection accuracy, empowering users to select the model
that best matches their specific needs.

Figure 8: Snapshots of marine$\mathcal{X}$’s open-sea teleportation
experiments in the presence of small and large waves.  Figure 9: Sequence of
snapshots of marine$\mathcal{X}$’s vision guided navigation in the marine
pool. Snapshots represented in Fig-a1-5 are captured with the external camera
whereas, snapshots in Fig-b1-5 are captured with marine$\mathcal{X}$’s onboard
camera.

The loss function of YOLOV5 is defined as follows:

$L_{yolo}=L_{box}+L_{cls}+L_{obj}$ (1)

where $L_{box}$, $L_{cls}$, and $L_{obj}$ denotes the bounding box regression,
classification, and confidence loss function respectively.

The bounding box regression is expressed as follows:

$\displaystyle
L_{box}=\lambda_{coord}\sum_{i=0}^{S^{2}}\sum_{j=0}^{B}I_{i,j}^{obj}b_{j}(2-w_{i}\times
h_{i})$ (2)
$\displaystyle\left[(x_{i}-x\wedge_{i}^{j})^{2}+(y_{i}-y\wedge_{i}^{j})^{2}+(w_{i}-w\wedge_{i}^{j})^{2}+(h_{i}-h\wedge_{i}^{j})^{2}\right]$

The classification loss is expressed as follows:

$L_{cls}=\lambda_{class}\sum_{i=0}^{S^{2}}\sum_{j=0}^{B}I_{i,j}^{obj}\sum_{c\in\text{classes}}p_{i}(c)\log(\hat{p}_{i}(c))$
(3)

Similarly, the confidence loss is expressed as below:

$\displaystyle
L_{obj}=\lambda_{noobj}\sum_{i=0}^{S^{2}}\sum_{j=0}^{B}I_{i,j}^{noobj}(c_{i}-c\wedge_{i})^{2}$
(4)
$\displaystyle+\lambda_{obj}\sum_{i=0}^{S^{2}}\sum_{j=0}^{B}I_{i,j}^{obj}(c_{i}-c\wedge_{i})^{2}$

where, $\lambda_{coord}$, $\lambda_{class}$, $\lambda_{noobj}$, and
$\lambda_{obj}$ are loss coefficient. $w$, $h$,$x$, and $y$ represents width,
height, center coordinates, respectively. $\hat{p}_{i}(c)$ shows the class
probability while $c$ shows the class category.

###  IV-B Control Strategies for Vision Guided Navigation

Control strategies for vision-guided navigation of marine$\mathcal{X}$ involve
the integration of computer vision algorithms with advanced control techniques
to enable precise and autonomous navigation in marine environments. The
control scheme is similar to the one used in [17]. The vision system extracts
relevant features from the camera images, such as objects of interest and
estimate the marine$\mathcal{X}$’s position and orientation. This information
serves as feedback for the control system. To generate control commands for
actuators, various control strategies are used, the PID control is a widely
used control technique for such problem. It is a classical feedback control
algorithm that is designed to regulate a system’s behavior by continuously
adjusting a control variable based on the difference between the desired
setpoint and the current measured value of a process variable. The main goal
of PID control is to bring the system’s output as close as possible to the
desired setpoint while maintaining stability.

The image obtained by the marine$\mathcal{X}$ front camera is passed to the
object detector, let $\mathcal{I}$ represent the detector output image. The
current position of the target object in $\mathcal{I}$ is represented by
$\mathcal{P}_{c}$ and the desired position of the target object in
$\mathcal{I}$ denotes by $\mathcal{P}_{d}$. The heading error function
$f_{e}(t)$ is defined as $f_{e}(t)=\mathcal{P}_{d}-\mathcal{P}_{c}$. As an
output, it provides the pixel error, that is used to correct the
marine$\mathcal{X}$ heading toward the target. To minimize the error function
$f_{e}(t)$, the PID control equation is defined as;

$u(t)=K_{\textrm{p}}f_{e}(t)+K_{\textrm{i}}\int_{0}^{t}f_{e}(t)\,dt+K_{\textrm{d}}\frac{d\;f_{e}(t)}{dt}$
(5)

Where $u(t)$ is the control output that will be applied to the
marine$\mathcal{X}$ at time $t$. The control signals $u(t)$ is typically used
to adjust the marine$\mathcal{X}$ velocity and steering commands to keep the
object within the camera’s field of view and track its movement accurately.
The terms, $K_{\textrm{p}}$, $K_{\textrm{i}}$, and $K_{\textrm{d}}$ represent
the proportional, integral and derivative gains, respectively. In Equ. 5, the
integral terms representing the accumulated error over time, it helps to
minimize the steady-state errors. The differential term computes the rate of
change of error with respect to time. It helps to dampen the system’s response
and improve stability. The PID control algorithm requires tuning of the the
$K_{\textrm{p}}$, $K_{\textrm{i}}$, and $K_{\textrm{d}}$, to achieve the
desired tracking performance. We tune these parameters in marine pool by
manually varying the values of these gains. While navigation, at each
iteration, the distance to the target is computed by measuring the depth. The
process will continue until the distance to the target vessel is less than
given threshold.

##  V Results and Discussions

We conducted extensive tests to validate the marine$\mathcal{X}$ design and
maneuvering capability in simulation (Fig 5) and in the marine pool with no
waves and streams. Moreover, to evaluate the operational capability of the
marine$\mathcal{X}$ in real scenarios, we also conducted the extensive tests
in the open sea environment. Fig 8 shows snapshots of marine$\mathcal{X}$
operating in open sea. In the teleportation mode, the marine$\mathcal{X}$
shows precise control in the marine pool environment with calm water (in the
absence of waves and stream). In the open sea environment it perform well in
the presence of small waves and light winds. In the large waves the
marine$\mathcal{X}$ navigate accurately, however if we increase the speed,
then it jumps on the water surface while navigation.

In autonomous mode, we tested the vision guided navigation approach (explained
in Sec. IV) in the marine pool, it accurately detect and navigate towards the
desired target location. Fig. 9 show the sequence of snapshots of visual
servoing in the marine pool. In open sea the autonomous navigation is
possible, however it required to navigate marine$\mathcal{X}$ on a slow speed
e.g. 1 knots at maximum. Moreover large waves and strong winds could effect
the navigation performance.

##  VI Conclusion

This study introduces marine$\mathcal{X}$, an unmanned surface vessel with a
catamaran design. Its robust hardware includes 3D printed hulls, an aluminum
frame, and a water-tight enclosure housing the electronics. The vessel’s
vision-guided navigation algorithm was validated through simulation, marine
pool, and open sea tests, exhibiting stable and robust performance across all
scenarios. Overall, marine$\mathcal{X}$ showcases the potential of marine
robotics and autonomous systems for various maritime applications.

## Acknowledgement

This work is supported by the Khalifa University of Science and Technology
under Award No. MBZIRC-8434000194, CIRA-2021-085, FSU-2021-019,
RC1-2018-KUCARS.

## References

  * [1] P. Johnston and M. Poole, “Marine surveillance capabilities of the autonaut wave-propelled unmanned surface vessel (usv),” in OCEANS 2017-Aberdeen, pp. 1–46, IEEE, 2017.
  * [2] A. Matos, E. Silva, N. Cruz, J. C. Alves, D. Almeida, M. Pinto, A. Martins, J. Almeida, and D. Machado, “Development of an unmanned capsule for large-scale maritime search and rescue,” in 2013 OCEANS-San Diego, pp. 1–8, IEEE, 2013.
  * [3] J. L. Villa, J. Paez, C. Quintero, E. Yime, and J. Cabrera, “Design and control of an unmanned surface vehicle for environmental monitoring applications,” in 2016 IEEE Colombian Conference on Robotics and Automation (CCRA), pp. 1–5, 2016.
  * [4] V. Jorge, R. Granada, R. Maidana, D. Jurak, G. Heck, A. Negreiros, D. Santos, L. Gonçalves, and A. Amory, “A survey on unmanned surface vehicles for disaster robotics: Main challenges and directions,” Sensors, vol. 19, p. 702, 02 2019.
  * [5] W. Al Maawali, A. Al Naabi, M. Al Yaruubi, A. Saleem, and A. Al Maashri, “Design and implementation of an unmanned surface vehicle for oil spill handling,” in 2019 1st International Conference on Unmanned Vehicle Systems-Oman (UVS), pp. 1–6, IEEE, 2019.
  * [6] A. Papanikolaou, Ship design: methodologies of preliminary design.  Springer, 2014.
  * [7] M. Caccia, “Autonomous surface craft: prototypes and basic research issues,” in 2006 14th Mediterranean Conference on Control and Automation, pp. 1–6, IEEE, 2006.
  * [8] Z. Liu, Y. Zhang, X. Yu, and C. Yuan, “Unmanned surface vehicles: An overview of developments and challenges,” Annual Reviews in Control, vol. 41, pp. 71–93, 2016.
  * [9] T. I. Fossen, Handbook of marine craft hydrodynamics and motion control.  John Wiley & Sons, 2011.
  * [10] J. H. Mei and M. Arshad, “A smart navigation and collision avoidance approach for autonomous surface vehicle,” 2017.
  * [11] M. Breivik and T. I. Fossen, “Path following for marine surface vessels,” in Oceans’ 04 MTS/IEEE Techno-Ocean’04 (IEEE Cat. No. 04CH37600), vol. 4, pp. 2282–2289, IEEE, 2004.
  * [12] M. Caccia, R. Bono, G. Bruzzone, E. Spirandelli, G. Veruggio, A. Stortini, and G. Capodaglio, “An autonomous craft for the study of sea-air interactions,” IEEE Robotics & Automation Magazine, vol. 12, no. 3, pp. 95–105, 2005\.
  * [13] H. Ferreira, A. Martins, A. Dias, C. Almeida, J. M. Almeida, and E. P. Silva, “Roaz autonomous surface vehicle design and implementation,” Robótica Controlo, Automação, instrumentação, 2007.
  * [14] J. E. Manley, A. Marsh, W. Cornforth, and C. Wiseman, “Evolution of the autonomous surface craft autocat,” in OCEANS 2000 MTS/IEEE conference and exhibition. Conference proceedings (Cat. No. 00CH37158), vol. 1, pp. 403–408, IEEE, 2000.
  * [15] J. Manley and S. Willcox, “The wave glider: A persistent platform for ocean science,” in OCEANS’10 IEEE SYDNEY, pp. 1–5, IEEE, 2010.
  * [16] M. Azzeri, F. Adnan, and M. M. Zain, “Review of course keeping control system for unmanned surface vehicle,” Jurnal Teknologi, vol. 74, no. 5, pp. 11–20, 2015.
  * [17] M. Ahmed, A. B. Bakht, T. Hassan, W. Akram, A. Humais, L. Seneviratne, S. He, D. Lin, and I. Hussain, “Vision-based autonomous navigation for unmanned surface vessel in extreme marine conditions,” in IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2023), pp. 1–7, 2023.
  * [18] K. He, G. Gkioxari, P. Dollar, and R. Girshick, “Mask R-CNN,” 2017.  IEEE International Conference on Computer Vision (ICCV), 2017.
  * [19] S. Ren, K. He, R. Girshick, and J. Sun, “Faster R-CNN: Towards real-time object detection with region proposal networks,” in Advances in Neural Information Processing Systems (NIPS), 2015.
  * [20] J. Redmon and A. Farhadi, “YOLOv3: An Incremental Improvement,” 2018\.  arXiv, 2018.
  * [21] G. Jocher et al., “YOLOv5,” 2022.  Ultralytics, Retrieved: November 2nd, 2022.


# Vision Transformers for Mobile Applications: A Short Survey

Nahid Alam*
Cohere for AI Community
Steven Kolawole*
ML Collective
Simardeep Sethi*
IIT Delhi  Nishant Bansali
Cohere for AI Community
Karina Nguyen
UC Berkeley

###### Abstract

Vision Transformers (ViTs) have demonstrated state-of-the-art performance on
many Computer Vision Tasks. Unfortunately, deploying these large-scale ViTs is
resource-consuming and impossible for many mobile devices. While most in the
community are building for larger and larger ViTs, we ask a completely
opposite question: How small can a ViT be within the tradeoffs of accuracy and
inference latency that make it suitable for mobile deployment? We look into a
few ViTs specifically designed for mobile applications and observe that they
modify the transformer’s architecture or are built around the combination of
CNN and transformer. Recent work has also attempted to create sparse ViT
networks and proposed alternatives to the attention module. In this paper, we
study these architectures, identify the challenges and analyze what really
makes a vision transformer suitable for mobile applications. We aim to serve
as a baseline for future research direction and hopefully lay the foundation
to choose the exemplary vision transformer architecture for your application
running on mobile devices.

**footnotetext: Equal contribution

_Keywords_ Vision Transformer $\cdot$ Attention $\cdot$ Sparse Vision
Transformer

##  1 Introduction

Inspired by the success of transformer Vaswani et al. (2017) models in Natural
Language Processing (NLP) application, A. Dosovitskiy et al. Dosovitskiy et
al. (2020) introduced Vision Transformer (ViT) for Computer Vision (CV)
applications. Vision transformer models have shown 77.9% to 81.3% Top-1
accuracy on ImageNet dataset Touvron et al. (2021a),Dosovitskiy et al.
(2020),Liu et al. (2021a) and have been used in many downstream image
recognition task such as classification Caron et al. (2021),Liu et al.
(2021b), object detection Carion et al. (2020), Li et al. (2021) and
segmentation Xie et al. (2021),Cheng et al. (2021). Although the Top-1
accuracy scores of these models are impressive, they are generally too big and
too slow to deploy on mobile devices Wang et al. (2022). These models’ massive
number of parameters is a burden to compute, storage, memory, and inference
latency of a mobile application. The Multi-Head Self-Attention (MHSA)
operation in the Transformer module is quadratic in nature. The MLP module in
ViT projects the embedding space by a factor of four, applies non-linearity,
and then projects it back to its original shape. As a result, the latency of
ViT models, in general, is unrealistic for edge devices such as iPhone, Google
Edge TPU (2022), NVIDIA Jetson Nano, Intel Edge devices such as Movidious
(2022), FPGA (2020) and Hexagon DSPs from Qualcomm etc.

The motivation for this work comes from our experience working with various
computer vision applications on mobile devices where CNNs are still prevalent.
While the applications in these domains can benefit from the improved
performance of a ViT-based backbone, compared to CNN, ViTs have 1.5-4x
inference latency Wang et al. (2022), Mehta and Rastegari (2021). Therefore
CNNs are the prevailing architecture of choice in those applications.

Recently, various architectures have been proposed specifically targeting CV
tasks in mobile devices that combine transformers with CNNs. In addition,
techniques such as quantization, pruning, distillation, etc., are applied to
an existing model to fit it in mobile devices Kurtz et al. (2020). Kuznedelev
et al. (2022a) demonstrated a training-aware pruning framework to sparsify
ViTs that achieves almost SOTA accuracy with 50% sparsity.

We aim to explore vision transformer architectures optimized for mobile
devices. We are specifically interested in their inference efficiency with
accuracy/latency tradeoffs. We identify a few common patterns in design
choices and challenges in building mobile-optimized ViTs and serve as a guide
for edge-optimized vision transformer research.

##  2 Related Work

Han et al. Han et al. (2022) did a comprehensive survey on Vision
Transformers. Still, their work focused on the traditional ViT architectures,
not on the ones specifically suitable for mobile applications. Wang et al.
Wang et al. (2022) looked into the state of Vision Transformer for mobile
devices from the inference perspective. Their work is designed to check if
traditional ViTs are suitable for mobile or not and have not looked into any
mobile-suitable ViTs other than T2T-ViT Yuan et al. (2021). In our work, we
look into 8 different Vision Transformers designed for mobile applications,
pruning frameworks for sparsifying ViTs, and alternatives to attention
networks that can further enhance inference efficiency for Vision
Transformers.

##  3 Vision Transformers for Mobile Applications

Mobile suitable vision transformers can be broadly classified into two
categories. First, changing the model post-training - techniques such as
quantization, pruning Han et al. (2015a), Han et al. (2015b) and a mix of
model sparsification techniques Kurtz et al. (2020) are applied. Second -
model architecture changes. This can be a mix of transformer+CNN model, MLP-
based models Touvron et al. (2021b), or sparse models Fedus et al. (2022).
This work focuses on the architectural changes that make vision transformers
suitable for mobile applications.

###  3.1 Exploring the Architectures

#### Receptive Field Increase

A common challenge in CV tasks is to process higher-resolution images for
better accuracy without additional compute costs. Both Efficient-ViT Cai et
al. (2022) and EdgeNeXt Maaz et al. (2022) propose design changes to tackle
this issue. Efficient-ViT consists of MobileNetV2 Sandler et al. (2018) Depth-
Wise Convolution (DWConv) layers followed by a linear attention module that
replaces Softmax attention. It is followed by a Feed Forward Network (FFN)
with deformable CNN. Similarly, EdgeNeXt proposes a Split Depth-wise Transpose
Attention (SDTA) encoder instead of the vanilla MHSA module. The SDTA encoder
splits the input tensors into multiple channel groups. It then utilizes DWConv
and self-attention across channel dimensions to effectively increase the
receptive field the model operates on.

#### Pooling Layers

A set of hybrid CNN+Transformer architectures uses pooling layers after the
attention module to decrease the inference latency. NextViT Li et al. (2022a)
consists of alternate Convolutional and Transformer blocks. The Convolutional
block uses Multi-head Convolution Attention (MHCA) formed of a grouped 3X3
Convolution operation and an MLP. The Transformer block uses MHSA consisting
of a pooling layer for the Key and Value vectors. Moreover, channel reduction
is applied to improve inference speed. PoolFormer Yu et al. (2022) suggests an
alternative token mixture module - MetaFormer, where the token mixture is
modified with a pooling layer, resulting in a similar accuracy with fewer
parameters compared to ViT.

#### Principles of CNN

LeViT Graham et al. (2021) brings the principles of CNN network to
transformers - specifically activation maps through decreasing resolution. It
passes the input through a 3x3 convolution and then does a shrinkage of the
attention module. Instead of positional embeddings, LeViT encodes the location
information through an attention bias term to the attention map. The training
process of LeViT is similar to DeiT, which uses a distillation token head
after the last stage. MobileViT Mehta and Rastegari (2021) introduces the
MobileViT module that is responsible for capturing the interaction of local
and global features of the image. The local representation is captured using
NxN convolutions with 1x1 point-wise convolution whose output feature map
serves as an input for the global feature capturing module.

#### Consistent Tensor Dimension

EfficientFormer Li et al. (2022b) brings a consistent feature dimension to the
token mixture. The overall network is divided per the tensor dimension; First,
based on 4D tensors. A Convolution layer termed MB4D is applied on
4-Dimensional tensors and, second, based on 3D tensors consisting of MHSA as a
token mixer for the transformer module. Embedding layers are used between
stages to project the token length to a lower dimension, alleviating the
dimension mismatch and thereby improving the inference speed. Figure 1 shows a
high-level view of these architectures described so far.

#### Parallel Layers

We found a category of models that execute specific layers in parallel to
improve time complexity. The two parallel branches of Mobile-Former Chen et
al. (2022a) extract local and global representations, respectively and
concatenate through a bridge architecture. MixFormer’s Chen et al. (2022b) two
parallel branches communicate with each other through channel interactions and
spatial interactions, providing complementary clues for better representation
learning in both branches.

#### Token Reduction.

Memory and inference latency in a transformer strongly correlate to the number
of tokens. But many of these tokens are redundant for the task at hand. Recent
work has demonstrated token reduction by pruning tokens Meng et al. (2021),
Fayyaz et al. (2021), combining tokens Kong et al. (2021), Ryoo et al. (2021).
All of these methods require training of the model, while ToMe Bolya et al.
(2022) proposes a technique for merging tokens based on similarity without any
further model training.

#### Integer Quantization

Quantization is used to decrease inference latency at edge devices. However,
an integer-only arithmetic operation on the vision transformer is an open
challenge. I-ViT Li and Gu (2022) addresses this gap by applying a dyadic
arithmetic pipeline to use integer-only arithmetic for linear operations. For
non-linear operations, I-ViT introduces 3 novel operations - Shiftmax,
ShiftGelu, and I-LayerNorm. Shiftmax serves as an alternative to the softmax
function. It uses the scaling factor of quantization obtained from the MatMul
operation and the quantized integer weight to get an integer-only value.
Similarly, ShiftGelu is an alternative to the Gelu activation function and
I-LayerNorm for an integer-only layer normalization operation that improves
top-1 accuracy and latency.

Figure 1: Abstract Vision Transformer Architectures From Left to Right:
Vanilla Transformer; Efficient-Former; PoolFormer; EdgeNext; EfficientViT;
LeViT; NextViT; MobileViT

###  3.2 Sparse Vision Transformers

One approach to building an optimized Vision Transformer is to build a Sparse
Neural Network (SNN) version of the dense model. SNN typically refers to Liu
and Wang (2023), Gale et al. (2019) weight sparsity, i.e. setting weights to
zero. This can be helpful when the model is over-parameterized for a given
task. SNN can also be based on activation sparsity which measures the number
of zeros after non-linearity, i.e, activation function Rhu et al. (2018).

Sparsity can be structured - where a block of weight matrix can either be
dense or sparse Gale et al. (2019). In unstructured sparsity, there is no
pattern to follow Kuzmin et al. (2019), Liu and Wang (2023). Unstructured
sparsity removes the least significant weights regardless of where they are -
leading to irregular sparse patterns. Han et el. Han et al. (2015b) proposed
the popular method of weight pruning at Neural Networks - training, pruning,
and retraining. This approach generally requires multiple iterations of
retraining to recover the lost accuracy. This is specifically challenging for
Vision Transformers since they are already hard to train and stabilize.

While CNNs allow for greater than 80% unstructured sparsity Singh and Alistarh
(2020), and up to 40% structured sparsity Liu et al. (2021c), before
significant accuracy drops, ViT sparsity is harder to achieve. Kuznedelev et
al. Kuznedelev et al. (2022b) showed that ViT models lose significant amounts
of accuracy in each pruning step. And recovering that lost accuracy is harder
for ViTs than CNN. To alleviate this issue, Frankle et al. in Lottery Ticket
Hypothesis [LTH] Frankle and Carbin (2018) showed that it is possible to find
a Sparse subnetwork (i.e. “winning tickets”) inside a Dense network that we
can train in isolation for full accuracy. Finding that sparse subnetwork,
though, is an NP-hard problem, therefore, requires an iterative pruning
process to get to that useful subnetwork. Chen et al. Chen et al. (2021)
demonstrated the use of an end-to-end dynamic sparse network to address the
challenges of LTH. The authors used ImageNet with DeiT-Tiny/Small/Base. They
demonstrated 50% model sparsity with DeiT-Small produces, saving 49.32% FLOPs
and 4.40% running time while attaining a surprising improvement of 0.28%
accuracy. Kuznedelev et al. Kuznedelev et al. (2022b) proposed the oViT
framework that iteratively prunes the model while finetuning. With oViT,
EfficientFormer-L1 with 50% sparsity achieves 78% Top-1 accuracy vs the dense
counterpart of 78.9% accuracy.

###  3.3 Alternatives to Attention

Recent work on finding alternatives to the attention module shows promising
results. Zhai et al. Zhai et al. (2021) proposed an attention-free transformer
architecture. The authors suggest replacing attention with gating and Softmax
or gating and explicit convolution. Michael et al. Poli et al. (2023) look to
find a subquadratic operator that can match the quality of the attention
network at scale. They showed that their attention-free network reaches
transformer quality with 20% less compute for language modeling tasks. Their
proposed subquadratic Hyena operators are twice as fast as highly optimized
attention at sequence length 8K and 100× faster at sequence length 64K, tested
on WIKITEXT103 and THE PILE dataset. Using these subquadratic operators as a
drop-in replacement for attention modules can be a direction for future
research.

###  3.4 Comparing Results

Figure 2: Top-1 Accuracy vs. Latency for Image Classification on ImageNet-1K
using CoreML on iPhone12

Figure 2 shows Top-1 accuracy vs. latency on several Vision Transformer models
that might be suitable for edge devices. These models are trained on
ImageNet-1K for 300 epochs with AdamW optimizer on an image resolution of
224x224. Latency is measured using the CoreML framework on an iPhone 12. Table
1 lists a few state-of-the-art models based on CNN, Hybrid, and pure
transformer-based architectures and their number of parameters.

Model | Parameters(M)
---|---
ResNet50 | 25.5
MobileNetv2 | 6.1
DeiT-T | 5.9
DeiT-S | 22.5
EdgeNeXt | 5.6
MobileViT-XS | 2.3
LeViT-256 | 18.9
EfficientFormer-L1 | 12.3
EfficientFormer-L3 | 31.3
EfficientFormer-L7 | 82.1
MobileFormer-214 | 9.4
PoolFormer-s12 | 12
PoolFormer-s24 | 21
PoolFormer-s36 | 31
EfficientViT | 10.9
NextViT-S | 31.7
NextViT-B | 44.8
NextViT-L | 57.8
Table 1: Number of model parameters on ImageNet classification

These results suggest that we have a few interesting choices for mobile vision
transformers within the accuracy-latency tradeoffs. For example,
EfficientFormer-L3 has an 82.4% accuracy with a considerably low latency of
3ms. In comparison, NextViT-S has an 82.5% accuracy on the classification
task, with a 3.5ms latency on CoreML. In our observation, a sub-20M parameter
model is a mixed CNN-transformer architecture, mainly because the sub-
quadratic alternatives to attention operators are still not prevalent in ViTs
Poli et al. (2023).

##  4 Conclusion and Future Work

We aim to serve as a bird’s-eye view of the current state of ViTs for mobile
applications. We surveyed ViTs that are specifically designed for mobile
applications. We identified a few different models with around 10M parameters
and reasonable latency-accuracy trade-offs. The majority of these models
reduce the time complexity of the MHSA module by modifying the attention
operation or completely removing it. ViT one-shot pruning is hard, and the
accuracy recovery process is challenging Kuznedelev et al. (2022b) \- leading
to the need for further research. Token reduction techniques, specifically the
ones without requiring further model training, might serve the purpose of the
mobile vision transformer community. Moreover, we think that finding
attention-free subquadratic operators that act as a drop-in replacements for
attention modules in transformers Poli et al. (2023) can be a research
direction worth exploring for mobile vision transformers.

## References

  * Vaswani et al. [2017] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In _Advances in Neural Information Processing Systems_ , pages 5998–6008, 2017.
  * Dosovitskiy et al. [2020] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al.  An image is worth 16x16 words: Transformers for image recognition at scale.  _arXiv preprint arXiv:2010.11929_ , 2020.
  * Touvron et al. [2021a] Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Hervé Jégou.  Training data-efficient image transformers & distillation through attention.  In _International Conference on Machine Learning_ , pages 10347–10357. PMLR, 2021a.
  * Liu et al. [2021a] Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo.  Swin transformer: Hierarchical vision transformer using shifted windows.  _CoRR_ , abs/2103.14030, 2021a.
  * Caron et al. [2021] Mathilde Caron, Hugo Touvron, Ishan Misra, Hervé Jégou, Julien Mairal, Piotr Bojanowski, and Armand Joulin.  Emerging properties in self-supervised vision transformers.  _CoRR_ , abs/2104.14294, 2021.
  * Liu et al. [2021b] Ze Liu, Jia Ning, Yue Cao, Yixuan Wei, Zheng Zhang, Stephen Lin, and Han Hu.  Video swin transformer.  _CoRR_ , abs/2106.13230, 2021b.
  * Carion et al. [2020] Nicolas Carion, Francisco Massa, Gabriel Synnaeve, Nicolas Usunier, Alexander Kirillov, and Sergey Zagoruyko.  End-to-end object detection with transformers.  _CoRR_ , abs/2005.12872, 2020.
  * Li et al. [2021] Yanghao Li, Chao-Yuan Wu, Haoqi Fan, Karttikeya Mangalam, Bo Xiong, Jitendra Malik, and Christoph Feichtenhofer.  Improved multiscale vision transformers for classification and detection.  _CoRR_ , abs/2112.01526, 2021.
  * Xie et al. [2021] Enze Xie, Wenhai Wang, Zhiding Yu, Anima Anandkumar, Jose M. Alvarez, and Ping Luo.  Segformer: Simple and efficient design for semantic segmentation with transformers.  _CoRR_ , abs/2105.15203, 2021.
  * Cheng et al. [2021] Bowen Cheng, Ishan Misra, Alexander G. Schwing, Alexander Kirillov, and Rohit Girdhar.  Masked-attention mask transformer for universal image segmentation.  _CoRR_ , abs/2112.01527, 2021.
  * Wang et al. [2022] Xudong Wang, Li Lyna Zhang, Yang Wang, and Mao Yang.  Towards efficient vision transformer inference: a first study of transformers on mobile devices.  In _Proceedings of the 23rd Annual International Workshop on Mobile Computing Systems and Applications_ , pages 1–7, 2022.
  * TPU [2022] TPU.  Edge TPU - Run Inference at the Edge | Google Cloud.  https://cloud.google.com/edge-tpu, 2022.
  * Movidious [2022] Movidious.  Intel Movidious VPU.  https://www.intel.com/content/www/us/en/products/docs/processors/movidius-vpu/myriad-x-product-brief.html?wapkw=movidius, 2022\.
  * FPGA [2020] FPGA.  Intel AI FPGA.  https://www.intel.com/content/www/us/en/products/details/fpga/stratix/10/nx.html, 2020\.
  * Mehta and Rastegari [2021] Sachin Mehta and Mohammad Rastegari.  Mobilevit: Light-weight, general-purpose, and mobile-friendly vision transformer.  _CoRR_ , abs/2110.02178, 2021.
  * Kurtz et al. [2020] Mark Kurtz, Justin Kopinsky, Rati Gelashvili, Alexander Matveev, John Carr, Michael Goin, William Leiserson, Sage Moore, Bill Nell, Nir Shavit, and Dan Alistarh.  Inducing and exploiting activation sparsity for fast inference on deep neural networks.  In Hal Daumé III and Aarti Singh, editors, _Proceedings of the 37th International Conference on Machine Learning_ , volume 119 of _Proceedings of Machine Learning Research_ , pages 5533–5543, Virtual, 13–18 Jul 2020. PMLR.
  * Kuznedelev et al. [2022a] Denis Kuznedelev, Eldar Kurtic, Elias Frantar, and Dan Alistarh.  ovit: An accurate second-order pruning framework for vision transformers, 2022a.  URL https://arxiv.org/abs/2210.09223.
  * Han et al. [2022] Kai Han, Yunhe Wang, Hanting Chen, Xinghao Chen, Jianyuan Guo, Zhenhua Liu, Yehui Tang, An Xiao, Chunjing Xu, Yixing Xu, et al.  A survey on vision transformer.  _IEEE transactions on pattern analysis and machine intelligence_ , 2022.
  * Yuan et al. [2021] Li Yuan, Yunpeng Chen, Tao Wang, Weihao Yu, Yujun Shi, Zi-Hang Jiang, Francis E.H. Tay, Jiashi Feng, and Shuicheng Yan.  Tokens-to-token vit: Training vision transformers from scratch on imagenet.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV)_ , pages 558–567, October 2021.
  * Han et al. [2015a] Song Han, Jeff Pool, John Tran, and William Dally.  Learning both weights and connections for efficient neural network.  _Advances in neural information processing systems_ , 28, 2015a.
  * Han et al. [2015b] Song Han, Huizi Mao, and William J Dally.  Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding.  _arXiv preprint arXiv:1510.00149_ , 2015b.
  * Touvron et al. [2021b] Hugo Touvron, Piotr Bojanowski, Mathilde Caron, Matthieu Cord, Alaaeldin El-Nouby, Edouard Grave, Gautier Izacard, Armand Joulin, Gabriel Synnaeve, Jakob Verbeek, and Hervé Jégou.  Resmlp: Feedforward networks for image classification with data-efficient training, 2021b.
  * Fedus et al. [2022] William Fedus, Jeff Dean, and Barret Zoph.  A review of sparse expert models in deep learning, 2022.  URL https://arxiv.org/abs/2209.01667.
  * Cai et al. [2022] Han Cai, Chuang Gan, and Song Han.  Efficientvit: Enhanced linear attention for high-resolution low-computation visual recognition.  _arXiv preprint arXiv:2205.14756_ , 2022.
  * Maaz et al. [2022] Muhammad Maaz, Abdelrahman Shaker, Hisham Cholakkal, Salman Khan, Syed Waqas Zamir, Rao Muhammad Anwer, and Fahad Shahbaz Khan.  Edgenext: Efficiently amalgamated cnn-transformer architecture for mobile vision applications.  _arXiv preprint arXiv:2206.10589_ , 2022.
  * Sandler et al. [2018] Mark Sandler, Andrew G. Howard, Menglong Zhu, Andrey Zhmoginov, and Liang-Chieh Chen.  Inverted residuals and linear bottlenecks: Mobile networks for classification, detection and segmentation.  _CoRR_ , abs/1801.04381, 2018.
  * Li et al. [2022a] Jiashi Li, Xin Xia, Wei Li, Huixia Li, Xing Wang, Xuefeng Xiao, Rui Wang, Min Zheng, and Xin Pan.  Next-vit: Next generation vision transformer for efficient deployment in realistic industrial scenarios.  _arXiv preprint arXiv:2207.05501_ , 2022a.
  * Yu et al. [2022] Weihao Yu, Mi Luo, Pan Zhou, Chenyang Si, Yichen Zhou, Xinchao Wang, Jiashi Feng, and Shuicheng Yan.  Metaformer is actually what you need for vision.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 10819–10829, 2022.
  * Graham et al. [2021] Benjamin Graham, Alaaeldin El-Nouby, Hugo Touvron, Pierre Stock, Armand Joulin, Hervé Jégou, and Matthijs Douze.  Levit: a vision transformer in convnet’s clothing for faster inference.  In _Proceedings of the IEEE/CVF international conference on computer vision_ , pages 12259–12269, 2021.
  * Li et al. [2022b] Yanyu Li, Geng Yuan, Yang Wen, Eric Hu, Georgios Evangelidis, Sergey Tulyakov, Yanzhi Wang, and Jian Ren.  Efficientformer: Vision transformers at mobilenet speed.  _arXiv preprint arXiv:2206.01191_ , 2022b.
  * Chen et al. [2022a] Yinpeng Chen, Xiyang Dai, Dongdong Chen, Mengchen Liu, Xiaoyi Dong, Lu Yuan, and Zicheng Liu.  Mobile-former: Bridging mobilenet and transformer.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 5270–5279, 2022a.
  * Chen et al. [2022b] Qiang Chen, Qiman Wu, Jian Wang, Qinghao Hu, Tao Hu, Errui Ding, Jian Cheng, and Jingdong Wang.  Mixformer: Mixing features across windows and dimensions, 2022b.
  * Meng et al. [2021] Lingchen Meng, Hengduo Li, Bor-Chun Chen, Shiyi Lan, Zuxuan Wu, Yu-Gang Jiang, and Ser-Nam Lim.  Adavit: Adaptive vision transformers for efficient image recognition, 2021\.
  * Fayyaz et al. [2021] Mohsen Fayyaz, Soroush Abbasi Koohpayegani, Farnoush Rezaei Jafari, Sunando Sengupta, Hamid Reza Vaezi Joze, Eric Sommerlade, Hamed Pirsiavash, and Juergen Gall.  Adaptive token sampling for efficient vision transformers, 2021.
  * Kong et al. [2021] Zhenglun Kong, Peiyan Dong, Xiaolong Ma, Xin Meng, Mengshu Sun, Wei Niu, Xuan Shen, Geng Yuan, Bin Ren, Minghai Qin, Hao Tang, and Yanzhi Wang.  Spvit: Enabling faster vision transformers via soft token pruning, 2021\.
  * Ryoo et al. [2021] Michael S Ryoo, AJ Piergiovanni, Anurag Arnab, Mostafa Dehghani, and Anelia Angelova.  Tokenlearner: Adaptive space-time tokenization for videos.  In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, _Advances in Neural Information Processing Systems_ , 2021.  URL https://openreview.net/forum?id=z-l1kpDXs88.
  * Bolya et al. [2022] Daniel Bolya, Cheng-Yang Fu, Xiaoliang Dai, Peizhao Zhang, Christoph Feichtenhofer, and Judy Hoffman.  Token merging: Your vit but faster, 2022.
  * Li and Gu [2022] Zhikai Li and Qingyi Gu.  I-vit: Integer-only quantization for efficient vision transformer inference.  _arXiv preprint arXiv:2207.01405_ , 2022.
  * Liu and Wang [2023] Shiwei Liu and Zhangyang Wang.  Ten lessons we have learned in the new "sparseland": A short handbook for sparse neural network researchers, 2023.
  * Gale et al. [2019] Trevor Gale, Erich Elsen, and Sara Hooker.  The state of sparsity in deep neural networks, 2019.
  * Rhu et al. [2018] Minsoo Rhu, Mike O’Connor, Niladrish Chatterjee, Jeff Pool, Youngeun Kwon, and Stephen Keckler.  Compressing dma engine: Leveraging activation sparsity for training deep neural networks.  pages 78–91, 02 2018.  doi:10.1109/HPCA.2018.00017.
  * Kuzmin et al. [2019] Andrey Kuzmin, Markus Nagel, Saurabh Pitre, Sandeep Pendyam, Tijmen Blankevoort, and Max Welling.  Taxonomy and evaluation of structured compression of convolutional neural networks, 2019.
  * Singh and Alistarh [2020] Sidak Pal Singh and Dan Alistarh.  Woodfisher: Efficient second-order approximation for neural network compression, 2020.
  * Liu et al. [2021c] Liyang Liu, Shilong Zhang, Zhanghui Kuang, Aojun Zhou, Jing-Hao Xue, Xinjiang Wang, Yimin Chen, Wenming Yang, Qingmin Liao, and Wayne Zhang.  Group fisher pruning for practical network compression, 2021c.
  * Kuznedelev et al. [2022b] Denis Kuznedelev, Eldar Kurtic, Elias Frantar, and Dan Alistarh.  ovit: An accurate second-order pruning framework for vision transformers, 2022b.
  * Frankle and Carbin [2018] Jonathan Frankle and Michael Carbin.  The lottery ticket hypothesis: Finding sparse, trainable neural networks.  2018\.
  * Chen et al. [2021] Tianlong Chen, Yu Cheng, Zhe Gan, Lu Yuan, Lei Zhang, and Zhangyang Wang.  Chasing sparsity in vision transformers: An end-to-end exploration, 2021\.
  * Zhai et al. [2021] Shuangfei Zhai, Walter Talbott, Nitish Srivastava, Chen Huang, Hanlin Goh, Ruixiang Zhang, and Josh Susskind.  An attention free transformer, 2021.
  * Poli et al. [2023] Michael Poli, Stefano Massaroli, Eric Nguyen, Daniel Y. Fu, Tri Dao, Stephen Baccus, Yoshua Bengio, Stefano Ermon, and Christopher Ré.  Hyena hierarchy: Towards larger convolutional language models, 2023.


# The Meta-C-Finite Ansatz

Robert Dougherty-Bliss

###### Abstract

The Fibonacci numbers satisfy the famous recurrence $F_{n}=F_{n-1}+F_{n-2}$.
The theory of C-finite sequences ensures that the Fibonacci numbers whose
indices are divisible by $m$, namely $F_{mn}$, satisfy a similar recurrence
for every positive integer $m$, and these recurrences have an explicit,
uniform representation. We will show that $a(mn)$ has a uniform recurrence
over $m$ for any C-finite sequence $a(n)$ and use this to automatically derive
some famous summation identities.

The Fibonacci numbers $F_{n}$ satisfy the famous recurrence
$F_{n}=F_{n-1}+F_{n-2}$. The sequence which takes every _other_ Fibonacci
number, $F_{2n},$ satisfies the similar recurrence
$F_{2n}=3F_{2(n-2)}-F_{2(n-2)}$. In fact, every sequence of the form $F_{mn}$
satisfies such a recurrence. Here are the first few:

$\displaystyle\begin{split}F_{n}&=F_{n-1}+F_{n-2}\\\
F_{2n}&=3F_{2(n-1)}-F_{2(n-2)}\\\ F_{3n}&=4F_{3(n-1)}+F_{3(n-2)}\\\
F_{4n}&=7F_{4(n-1)}-F_{4(n-2)}\\\ F_{5n}&=11F_{5(n-1)}+F_{5(n-2)}.\end{split}$
(1)

If we look closely at the coefficients that appear—or plug them into the OEIS
[7]—there seems to be a general recurrence:

$F_{mn}=L_{m}F_{m(n-1)}+(-1)^{m+1}F_{m(n-2)}.$ (2)

This conjecture is right on the money, and we can prove it a dozen different
ways—Binet’s formula, induction, generatingfunctionology—but the _outline_ is
more interesting.

We began with a sequence which satisfied a nice recurrence ($F_{n}$), examined
recurrences for a family of related sequences $(F_{mn}$), then noticed that
the coefficients on the recurrences satisfied a _meta pattern_ (equation (2)).
This outline holds for any sequence which satisfies a linear recurrence
relation with constant coefficients. Such sequences are called _C-finite_ [8,
4].

The remainder of the paper is organized as follows. Section 1 gives a brief
overview of C-finite sequences, Section 2 proves that an analogue of (2) holds
for any C-finite sequence, Section 4 shows that a similar property holds for
products of C-finite sequences, and Section 3 applies some of our results to
produce infinite families of summation identities.

##  1 The C-finite ansatz

The theory of C-finite sequences is beautifully laid out in [4] and [8]. What
follows is a brief description of the principle results. For simplicity,
assume that everything we do is over an algebraically closed field such as the
complex numbers.

Given a sequence $a(n)$, let $N$ be the shift operator defined by

$Na(n)=a(n+1).$

We say that $a(n)$ is _C-finite_ if and only if there exists a polynomial
$p(x)$ such that $p(N)a(n)=0$ for all $n\geq 0$. We say that $p(x)$
_annihilates_ $a(n)$. For example, $x^{2}-x-1$ annihilates the Fibonacci
sequence $F(n)$ and $x-2$ annihilates the exponential sequence $2^{n}$. The
set of all polynomials which annihilate a fixed $a(n)$ is an ideal. The
generator of this ideal is the _characteristic polynomial_ of $a(n)$, and we
call its degree the degree (or order) of $a(n)$.

Every C-finite sequence has a closed-form expression as a sum of polynomials
times exponential sequences. More specifically,

$a(n)=\sum_{k=1}^{m}f_{k}(n)r_{k}^{n},$

where $r_{1},r_{2},\dots,r_{m}$ are the distinct roots of the characteristic
equation of $a(n)$ and $f_{k}(n)$ is a polynomial in $n$ with degree less than
or equal to the multiplicity of the root $r_{k}$. We call these formulas
_Binet-type formulas_ after Binet’s famous formula for the Fibonacci numbers.
For example, $(x-2)^{2}$ is an annihilating polynomial of any sequence $a(n)$
which satisfies the recurrence $a(n+2)=4a(n+1)-4a(n)$, and this implies
$a(n)=(\alpha+\beta n)2^{n}$ for some constants $\alpha$ and $\beta$.

We can go the other way and derive an annihilating polynomial from a closed
form expression. A term of the form $n^{d}r^{n}$ is annihilated by
$(x-r)^{d+1}$, so for each exponential $r^{n}$ in the closed form, look for
the highest power $n^{d}$ which is multiplied by $r^{n}$ and write down
$(x-r)^{d+1}$. For example, the sequence $a(n)=n3^{n}-\frac{n^{2}}{2}+5^{n}$
is annihilated by $(x-3)^{2}(x-1)^{3}(x-5)$.

Finally, if $a(n)$ and $b(n)$ are two C-finite sequences, then so are the
following:

$a(n)b(n)\qquad a(n)\pm b(n)\qquad\sum_{k=0}^{n}a(k)b(n-k).$

C-finite sequences are a special subclass of _holonomic sequences_ , sequences
which satisfy a linear recurrence with _polynomial coefficients_ [3].
Holonomic sequences satisfy very similar properties, but do not have the
readily computable closed forms which we need here.

##  2 Uniform recurrences

First up, we will prove the analogue of (2) for arbitrary C-finite sequences.

######  Proposition 1.

If $a(n)$ is a C-finite sequence of order $d$, then $n\mapsto a(nm)$ satisfies
a recurrence of the form

$a(nm)=\sum_{k=1}^{d}c_{k}(m)a((n-k)m),$ (3)

where $c_{k}(m)$ is C-finite with respect to $m$ and has order at most
${d\choose k}$. The sequence $c_{1}(m)$ always satisfies the same recurrence
as $a(n)$ itself, and $c_{d}(k)=\omega^{k}$, where $\omega$ is $(-1)^{d}$
times the constant coefficient of the characteristic polynomial of $a(n)$.

The following proof is constructive given the roots of the characteristic
polynomial of $a(n)$, but [1] gives formulas for $c_{k}(m)$ in terms of
partial Bell polynomials without reference to the roots.

###### Proof.

The Binet-type formula for $a(n)$ is a linear combination of terms of the form
$n^{i}r^{n}$ where $i$ is a nonnegative integer and $r$ is a root of the
characteristic polynomial of $a(n)$. Thus, the Binet-type formula for $a(nm)$
is a linear combination of terms of the form $(nm)^{i}r^{nm}$, which is
equivalently a linear combination of terms of the form $n^{i}(r^{m})^{n}$. The
only thing that has changed is the exponential terms themselves, so if

$\prod_{k=1}^{d}(x-r_{k})$

is the characteristic polynomial of $a(n)$ with possibly repeated roots
$r_{1},\dots,r_{d}$, then

$\prod_{k=1}^{d}(x-r_{k}^{m}).$ (4)

annihilates $n\mapsto a(nm)$. From the elementary theory of polynomials, the
coefficients of (4) are elementary symmetric functions of the roots
$r_{k}^{m}$. C-finite sequences are closed under multiplication and addition,
so the coefficients of the polynomial are C-finite with respect to $m$.

To obtain the degree bound, recall that the coefficient on $x^{d-i}$ in (4)
equals $(-1)^{i}e_{i}(r_{1}^{m},\dots,r_{d}^{m})$, where
$e_{i}(r_{1}^{m},\dots,r_{d}^{m})$ is the sum of all products of $i$ distinct
$r_{k}^{m}$. Each of these products is of the form $\alpha^{m}$ for some
constant $\alpha$. The number of such terms is an upper bound on the degree of
the sequence with respect to $m$, and there are exactly ${d\choose i}$ of
them.

Finally, note that the coefficient on $x^{d-1}$ is precisely the sum
$\sum_{k}r_{k}^{m}$, which is annihilated by the characteristic polynomial of
$a(n)$ itself, and the coefficient on $x^{d-d}$ is precisely the product
$(r_{1}r_{2}\dots r_{d})^{m}$. ∎

### Example: Perrin numbers

The Perrin numbers $P(n)$ are a third-order C-finite sequence defined by

$\displaystyle P(0)=0\quad$ $\displaystyle P(1)=0\quad P(2)=2$ $\displaystyle
P(n+3)$ $\displaystyle=P(n+1)+P(n).$

They are sometimes called the “skipponaci” numbers. They satisfy the
interesting property that $p$ divides $P(p)$ for every prime $p$. Tracing
through the above proof reveals the meta-recurrence

$P(mn)=P(m)P(m(n-1))+c(m)P(m(n-2))+P(m(n-3)),$ (5)

where $c(m)$ is A078712 in the OEIS.

### Example: General second-order

Let $a(n)$ be annihilated by $(x-r_{1})(x-r_{2})$ for distinct reals $r_{1}$
and $r_{2}$. The proof of Proposition 1 shows that $n\mapsto a(mn)$ is
annihilated by

$(x-r_{1}^{m})(x-r_{2}^{m})=x^{2}-(r_{1}^{m}+r_{2}^{m})x+(r_{1}r_{2})^{m}.$

In particular, if $r_{1}$ and $r_{2}$ are the golden ratio and its conjugate,
respectively, then $r_{1}^{m}+r_{2}^{m}=L_{m}$ is the $m$th Lucas number, and
$r_{1}r_{2}=-1$. This recovers (1).

### Example: Square Fibonacci

The square Fibonacci numbers $F_{n}^{2}$ are also C-finite. Going through the
steps of the above proof and consulting the OEIS reveals the following general
identity:

$F_{mn}^{2}=(5F_{m}^{2}+3(-1)^{m})(F_{m(n-1)}^{2}-(-1)^{m}F_{m(n-2)}^{2})+(-1)^{m}F_{m(n-3)}^{2}.$
(6)

### Example: Tribonacci

Consider the sequence $T_{n}$ defined by

$\displaystyle T_{0}$ $\displaystyle=0\quad T_{1}=0\quad T_{2}=1$
$\displaystyle T_{n}$ $\displaystyle=T_{n-1}+T_{n-2}+T_{n-3}.$

The family of sequences $n\mapsto T_{nm}$ satisfy the following recurrences:

$\displaystyle T_{n}$ $\displaystyle=T_{n-1}+T_{n-2}+T_{n-3}$ $\displaystyle
T_{2n}$ $\displaystyle=3T_{2(n-1)}+T_{2(n-2)}+T_{2(n-3)}$ $\displaystyle
T_{3n}$ $\displaystyle=7T_{3(n-1)}-5T_{3(n-2)}+T_{3(n-3)}$ $\displaystyle
T_{4n}$ $\displaystyle=11T_{4(n-1)}+5T_{4(n-2)}+T_{4(n-3)}$ $\displaystyle
T_{5n}$ $\displaystyle=21T_{5(n-1)}+T_{5(n-2)}+T_{5(n-3)}$ $\displaystyle
T_{6n}$ $\displaystyle=39T_{6(n-1)}-11T_{6(n-2)}+T_{6(n-3)}.$

In general,

$T_{nm}=c_{1}(m)T_{(n-1)m}+c_{2}(m)T_{(n-1)m}+T_{(n-2)m},$

where

$\displaystyle c_{1}(1)$ $\displaystyle=1\quad c_{1}(2)=3\quad c_{1}(3)=7$
$\displaystyle c_{1}(m)$ $\displaystyle=c_{1}(m-1)+c_{1}(m-2)+c_{1}(m-3)$

and

$\displaystyle c_{2}(1)$ $\displaystyle=1\quad c_{1}(2)=1\quad c_{1}(3)=-5$
$\displaystyle c_{2}(m)$ $\displaystyle=-c_{2}(m-1)-c_{2}(m-2)+c_{2}(m-3).$

The sequences $c_{k}(m)$ were found via guessing. However, Proposition 1
establishes that these sequences _are_ C-finite, and so proving our guess
requires that we check only finitely many terms. In this case we must check no
more than double the maximum degree, which is 6 terms. We have produced just
enough examples above to constitute a proof.

##  3 Uniform sums

The Fibonacci numbers satisfy the famous summation identity

$\sum_{k=0}^{n}F_{k}=F_{n+2}-1.$ (7)

There are as many ways to prove this identity as there are articles devoted to
evaluating related Fibonacci sums [5, 6, 2], but the most useful method at
this juncture is the following method outlined in [4]. The annihilating
polynomial of $F_{n}$ can be written as

$x^{2}-x-1=(x-1)x-1.$

Applying this to $F_{n}$ shows that $F_{n}=(x-1)F_{n+1}=F_{n+2}-F_{n+1}$. If
we sum over $n$, then the right-hand side telescopes and we recover (7). In
general, if $p(x)$ annihilates $a(n)$ and $p(1)\neq 0$, then we can write
$p(x)=(x-1)q(x)+p(1)$ for some easily-computable polynomial $q(x)$. Applying
this to $a(n)$ shows that $a(n)=(x-1)b(n)$ where $b(n)=-q(x)a(n)/p(1)$.
Summing over $n$ yields

$\sum_{0\leq k<n}a(k)=b(n)-b(0).$

From this idea, the uniform recurrences we have derived for sequences of the
form $n\mapsto a(mn)$ and $n\mapsto a(ni)a(nj)$ will help us discover uniform
summation identities.

Here is one such identity for the Perrin numbers, using (5).

######  Proposition 2.

The Perrin numbers $P(n)$ satisfy

$\sum_{0\leq
k<n}P(mn)=\frac{(P(n)-3)(1-P(m)-c(m))+P(n+1)(1-P(m))+P(n+2)-2}{P(m)+c(m)},$

where $c(m)$ is A078712 in the OEIS.

Using (6), we can quickly rediscover the following infinite family of sums for
the square of the Fibonacci numbers.

######  Proposition 3.

If $m$ is odd, then

$\sum_{0\leq k<n}F_{mk}^{2}=\frac{F_{mn}F_{m(n-1)}}{L_{m}}.$

###### Proof.

Using (6), we obtain

$\sum_{0\leq
k<n}F_{mk}^{2}=\frac{F_{mn}^{2}(7-10F_{m}^{2})+(F_{m(n+1)}^{2}-F_{m}^{2})(4-5F_{m}^{2})+F_{m(n+2)}^{2}-F_{2m}^{2}}{10F_{m}^{2}-8}.$

This is far from the most economical representation. First, the numerator here
contains $(5F_{m}^{2}-4)F_{m}^{2}-F_{2m}^{2}$. It is easy to check that

$(5F_{m}^{2}-4)F_{m}^{2}-F_{2m}^{2}=-8F_{m}^{2}\frac{(-1)^{m}+1}{2},$ (8)

so the expression on the left vanishes when $m$ is odd. We are down to

$\frac{F_{mn}^{2}(7-10F_{m}^{2})+F_{m(n+1)}^{2}(4-5F_{m}^{2})+F_{m(n+2)}^{2}}{10F_{m}^{2}-8}.$

Applying the general recurrence (1) to $F_{m(n+2)}$ and simplifying the result
brings us to

$\frac{F_{mn}^{2}(8-10F_{m}^{2})+F_{m(n+1)}^{2}((4-5F_{m}^{2})+L_{m}^{2})+2F_{mn}L_{m}F_{m(n+1)}}{10F_{m}^{2}-8}.$

When $m$ is odd, the identity $4-5F_{m}^{2}+L_{m}^{2}=0$ follows from dividing
(8) by $F_{m}^{2}$ and recalling that $L_{m}=F_{2m}/F_{m}$. Using this and
simplifying gives

$\frac{F_{mn}(-L_{m}F_{mn}+F_{m(n+1)})}{L_{m}},$

and applying the general recurrence (1) once more to $F_{m(n+1)}$ gives us the
final answer $F_{mn}F_{m(n-1)}/L_{m}$. ∎

##  4 Uniform products

The proof of Proposition 1 relied on little more than the identity
$r^{mn}=(r^{m})^{n}$ and some structural facts about C-finite sequences.
Unsurprisingly, these ideas apply to other settings. The below proposition
shows how to apply the idea to prove that sequences of the form $n\mapsto
a(ni)a(nj)$ also satisfy meta C-finite recurrences.

######  Proposition 4.

If $a(n)$ is C-finite of degree $d$ whose characteristic polynomial has $m$
distinct roots, then $P_{i,j}(n)=a(ni)a(nj)$ satisfies a recurrence of the
form

$P_{i,j}(n)=\sum_{k=1}^{m(2d-m)}c_{k}(i,j)P_{i,j}(n-k),$

where each $c_{k}(i,j)$ is C-finite with respect to $i$ and $j$ and
$c_{k}(i,j)=c_{k}(j,i)$. The sequence $c_{k}(i,j)$ has order (with respect to
$i$ or $j$) no more than ${d\choose k}$.

###### Proof.

Write the characteristic polynomial of $a(n)$ as
$\prod_{k=1}^{m}(x-r_{k})^{d_{k}+1}$ where the $r_{k}$ are distinct and
$d_{1}+d_{2}+\cdots+d_{m}=d-m$. Then,

$a(n)=\sum_{k=1}^{m}p_{k}(n)r_{k}^{n},$

where $p_{k}$ is a polynomial in $n$ of degree $d_{k}$ or less. Therefore

$P_{i,j}(n)=\sum_{1\leq k,v\leq m}p_{k}(in)p_{v}(jn)(r_{k}^{i}r_{v}^{j})^{n}.$

Immediately, we see that $P_{i,j}(n)$ is annihilated by

$\prod_{1\leq k,v\leq m}(x-r_{k}^{i}r_{v}^{j})^{d_{k}+d_{v}+1},$ (9)

a polynomial of degree $\sum_{k,v}(d_{k}+d_{v}+1)=m(2d-m)$. The coefficients
of this polynomial are elementary symmetric polynomials in the variables
$\\{r_{k}^{i}r_{v}^{j}\\}_{1\leq k,v\leq d}$, and therefore C-finite with
respect to $i$ and $j$ by the C-finite closure properties. The roots
$r_{k}^{i}r_{v}^{j}$ are symmetric in $i$ and $j$, so the coefficient
sequences are as well.

The coefficient on $x^{D-k}$ is essentially the sum of all products of $k$
distinct elements from $\\{r_{k}^{i}r_{v}^{j}\\}_{1\leq k,v\leq d}$. As a
sequence in $i$ the $r_{v}^{j}$ factors are irrelevant: The coefficient will
be annihilated by the characteristic polynomial for the sum of all products of
$k$ distinct elements from $\\{r_{k}^{i}\\}_{1\leq k\leq d}$. Each term of
this latter sum is of the form $\alpha^{i}$ for some constant $\alpha$, and
there are no more than ${d\choose k}$ distinct values of $\alpha$. Therefore
$c_{k}(i,j)$ has order no more than ${d\choose k}$ with respect to $i$ (and
also $j$). ∎

The previous proof can be slightly modified to produce a stronger statement.
Namely, if we split the product (9) into diagonal and off-diagonal terms, we
get the following corollary.

######  Corollary 1.

Let $a(n)$ be a C-finite sequence of degree $d$ whose characteristic
polynomial has $m$ distinct roots. Then $n\mapsto a(ni)a(nj)$ is annihilated
by a polynomial $C_{i,j}(x)$ which factors as

$C_{i,j}(x)=L_{i+j}(x)R_{i,j}(x),$ (10)

where $\deg L_{i+j}=2d-m$ and $\deg R_{i,j}=(m-1)(2d-m)$. The coefficients of
$L_{i+j}(x)$ are C-finite sequences in $i+j$ and the coefficients of
$R_{i,j}(x)$ are C-finite sequences which are symmetric in $i$ and $j$.

There is one case of this corollary worth highlighting. Now that we know these
annihilating polynomials with C-finite coefficients exist, we could find them
by computing enough examples and guessing a pattern. However, if the degrees
of $L_{i+j}(x)$ and $R_{i,j}(x)$ are the same, then it is not always clear
which factor is $L$ and which factor is $R$ in a given example. This happens
when $2d-m=(m-1)(2d-m)$. Since $m\leq d$, the interesting solution is $m=2$.
Thus sequences with exactly two roots in their characteristic polynomial
should be handled “manually.” We will show one example.

### Example: Second-order annihilators

Let $a(n)$ be a C-finite sequence annihilated by the quadratic
$(x-r_{1})(x-r_{2})$ where $r_{1}\neq r_{2}$. Then $n\mapsto a(ni)a(nj)$ is
annihilated by

$(x^{2}-\mathcal{L}(i+j)x+(r_{1}r_{2})^{i+j})(x^{2}-(r_{1}r_{2})^{j}\mathcal{L}(i-j)x+(r_{1}r_{2})^{i+j})$

where $\mathcal{L}(n)=r_{1}^{n}+r_{2}^{n}$. If $a(n)=F(n)$ equals the $n$th
Fibonacci number, then $\mathcal{L}(n)=L(n)$ is the $n$th Lucas number,
$r_{1}r_{2}=-1$, and we obtain the annihilator

$(x^{2}-L(i+j)x+(-1)^{i+j})(x^{2}-(-1)^{j}L(i-j)x+(-1)^{i+j}).$

##  5 Computer demo

This article is joined by a corresponding Maple package MetaCfinite,
obtainable from GitHub at https://github.com/rwbogl/MetaCfinite. With
MetaCfinite, nearly all the propositions described in this article can be
explored and checked empirically.

### Guessing uniform recurrences

Suppose that we want to discover (1) and the corresponding general pattern.
The following Maple commands compute the five recurrences from (1):

        Fib := [[0, 1], [1, 1]:
        mSect(Fib, 1, 0); # [[0, 1], [1, 1]]
        mSect(Fib, 2, 0); # [[0, 1], [3, -1]]
        mSect(Fib, 3, 0); # [[0, 2], [4, 1]]
        mSect(Fib, 4, 0); # [[0, 3], [7, -1]]
        mSect(Fib, 5, 0); # [[0, 5], [11, 1]]

We are trying to guess the pattern followed by $1,3,4,7,11$, and
$1,-1,1,-1,1$. The following command does this for us:

        MetaMSect(Fib, 0); # [[[1, 3], [1, 1]], [[1], [-1]]]

This tells us that, for example, the coefficient on $F_{m(n-1)}$ is a sequence
$L_{m}$ which begins $L_{1}=1$, $L_{2}=3$, and satisfies
$L_{m}=L_{m-1}+L_{m-2}$. These are the Lucas numbers.

### Uniform summation identities

The procedure polysum(a, n, p, x computes an expression for $\sum_{0\leq
k<n}a(k)$ where $a(n)$ is a C-finite sequence with characteristic polynomial
$p(x)$. For example, the following command derives the famous identity (7):

        polysum(F, n, x^2 - x - 1, x); # F(n + 1) - F(1).

This is most powerful when joined with uniform recurrences found by MetaMSect.
For instance, the sequence $n\mapsto F(mn)$ has characteristic polynomial
$p_{m}(x)=x^{2}-L(m)x-(-1)^{m+1}$. The following commands derive a summation
identity for $\sum_{0\leq k<n}F(mk)$:

        polysum(Fm, n, x^2 - L(m) * x - (-1)^(m + 1), x);
             (Fm(n) - Fm(0)) (1 - L(m)) + Fm(n + 1) - Fm(1)
           - ----------------------------------------------
                                           m
                            1 - L(m) + (-1)

That is, we have automatically derived the famous identity

$\sum_{0\leq k<n}F(mk)=\frac{F(mn)(1-L(m))+F(m(n+1))-F(m)}{L(m)-1-(-1)^{m}}.$

##  6 Conclusion

We have used the theory of C-finite sequences to establish _meta-facts_ about
the recurrences C-finite sequences satisfy. Namely, we have shown that the
recurrences satisfied by $n\mapsto a(nm)$ and $n\mapsto a(ni)a(nj)$ are
uniform in a C-finite sense. This allowed us to state uniform families of
summation identities for some C-finite sequences.

The summation identities our methods derive are automatic and uniform, but we
do not claim that they are the “best possible.” For instance, the first
expression obtained for $\sum_{k=0}^{n-1}F_{mk}^{2}$ in Proposition 3 is quite
cumbersome compared to the final answer:

$\frac{F_{mn}^{2}(7-10F_{m}^{2})+(F_{m(n+1)}^{2}-F_{m}^{2})(4-5F_{m}^{2})+F_{m(n+2)}^{2}-F_{2m}^{2}}{10F_{m}^{2}-8}=\frac{F_{mn}F_{m(n-1)}}{L_{m}}.$

It still takes some (semi-automatic) sweat to discover this reduction. Can we
automatically discover and prove such “complex = simple” identities? And might
this apply to more complex sums, such as $\sum_{k=0}^{n-1}F_{mk}^{5}$? The
answer is likely yes—and perhaps a C-finite simplification algorithm already
exists—but we leave this as an open problem.

Finally, the author would like to acknowledge Doron Zeilberger for bringing
these problems to his attention and providing encouragement.

## References

  * [1] Birmajer, D., Gil, J.B. and Weiner, M.D., 2015. Linear recurrence sequences with indices in arithmetic progression and their sums. arXiv preprint arXiv:1505.06339.
  * [2] Frontczak, R., 2018. Sums of powers of Fibonacci and Lucas numbers: A new bottom-up approach. Notes on Number Theory and Discrete Mathematics, 24(2), pp.94-103.
  * [3] Kauers, Manuel, 2013. The Holonomic Toolkit. In Computer Algebra in Quantum Field Theory (pp. 119-144). Springer, Vienna.
  * [4] Kauers, Manuel and Paule, Paule. (2010). _The Concrete Tetrahedron: Symbolic sums, Recurrence Equations, Generating Functions, Asymptotic Estimates._ Springer.
  * [5] Layman, J.W., 1977. Certain general binomial-Fibonacci sums. Fibonacci Quart, 15(3), pp.362-366.
  * [6] Melham, R., 1999. Sums involving Fibonacci and Pell numbers. Portugaliae Mathematica, 56(3), pp.309-318.
  * [7] OEIS Foundation Inc. (2022), The On-Line Encyclopedia of Integer Sequences, Published electronically at http://oeis.org.
  * [8] Zeilberger, Doron., 2013. The C-finite ansatz. The Ramanujan Journal, 31(1), pp. 23-32.