# Has Your FaaS Application Been Decommissioned Yet? - A Case Study on the
Idle Timeout in Function as a Service Infrastructure

Kim Long Ngo  York University
Toronto, Canada
<EMAIL_ADDRESS>Joydeep Mukherjee  California Polytechnic State University
CA, United States
<EMAIL_ADDRESS>Zhen Ming (Jack) Jiang  York University
Toronto, Canada
<EMAIL_ADDRESS>Marin Litoiu  York University
Toronto, Canada
<EMAIL_ADDRESS>
###### Abstract

Function as a Service (FaaS) is a new cloud technology with automated resource
management. Different from traditional cloud computing, each FaaS cloud
function can only run a fixed period of time before being decommissioned.
Furthermore, FaaS cloud providers often update their platforms (e.g., idle
timeout). These changes and their associated impact are not transparent and
could potentially impact the execution of the cloud functions. Hence, in this
paper, we develop a methodology to characterize the cloud function idle
timeout which is the duration a FaaS cloud provider keeps a cloud function
instance alive without serving active traffic. Our study was conducted on
three popular FaaS platforms, namely AWS Lambda, IBM and Azure Cloud Function.
Moreover, we also report how long a cloud function instance can be kept alive
when a user regularly polls the instance. Experimental results show that the
idle timeout period has evolved from 01/2020 till 01/2022.

##  I Introduction

The software industry has evolved rapidly with the transformation from
monolithic architecture operating on Virtual Machines (VM) to Microservices
running on light-weight containers such as Docker. To relieve the software
engineers from operational tasks such as resource management, a new technology
called Function as a Service (FaaS) was popularized since 2014. FaaS is an
event-driven cloud platform where software engineers can focus on business
logic and leave the infrastructure management to cloud providers [1].

The automated resource management feature brings both advantages and
challenges to cloud subscribers. On one hand, software engineers can be
relieved from resource management tasks. On the other hand, they do not have
the full control over the infrastructure. Without access to traditional
technologies like VMs or Containers, the engineers may not know when their
cloud function instances are recycled. When a cloud function is first invoked,
cloud platform needs to start up a container for execution. This process
introduces additional delay in function execution and is referred as cold
start. Cold start can occur when a cloud function first started or a cloud
instance is left idle beyond a certain time (idle timeout) or while scaling up
the application. Since cold start introduces execution delays, the more cold
start an application experiences, the more overhead is added to the overall
response time. As a consequence, knowing when a cloud function instance is
decommissioned will help engineers to better design their software systems.

To make FaaS an abstract platform, cloud providers do not specify their
underlying implementation including how long a cloud function can be idle.
However, researchers have shown the importance of knowing FaaS runtime
properties and partially characterized the FaaS function instance’s idle
timeout [4], [5], [6]. Industry practitioners also studied this aspect and
reported their experimental results on the web blogs [7], [8], [9]. These
studies are helpful to software engineers since they provide in-depth
knowledge about FaaS runtime. Moreover, our experimental results show that
FaaS providers regularly update their implementations. For example, our study
between 01/2020 and 01/2022 detected that AWS Lambda cloud function instance
idle timeout has been reduced from 10 to 5 minutes and this was not
communicated.

In this paper, we characterize FaaS instance idle timeout by presenting a
methodology to measure this duration up to minute-accuracy. To keep the cloud
function instance from decommissioning, a common workaround is the keep-alive
technique which is to poll the cloud function at a regular interval to
preserve the infrastructure [5]. We study the impact of applying the keep-
alive technique on the cloud function idle timeout. Furthermore, we also
measure the cloud function’s instance idle timeout at different times (i.e.,
checkpoints) from 01/2020 to 01/2022 and report the evolutionary changes. Our
experiments were carried out on three popular cloud platforms, namely AWS
Lambda (AWS), IBM Cloud Function (IBM) and Azure Cloud Function (Azure). The
contributions of our research are:

  * •

Presenting a method to measure the cloud function idle timeout with minute-
accuracy by extending the state of the art method [4].

  * •

Measuring the cloud function instance maximum idle timeout when the keep-alive
technique is used and based on this finding, we advise software engineers in
which use case they should use the keep-alive technique.

  * •

Characterizing the cloud function instance idle timeout changes over a period
of two years (01/2020 - 01/2022).

With our methodology, software engineers can reproduce the experiments to
measure the up-to-date cloud function idle timeout or design similar
approaches to examine other FaaS’ characteristics.

The rest of the paper is organized as follow: Section II introduces the
background and related work. Section III discusses our methodology to measure
cloud function instance idle timeout. Section IV presents the experimental
setups used in our studies. Section V reports the evaluation results. Section
VI summarizes our findings and highlights the lessons learnt. Finally, Section
VII concludes our research work.

##  II Background and Related Work

In this section, we first provide an overview of the FaaS in Section II-A.
Then we discuss about the related work in Section II-B.

###  II-A Background

FaaS is a new cloud technology that automatically manages the computing
resources. When traffic first arrives to a cloud function, FaaS platform will
provision, deploy the source code and initialize the cloud function instance
for execution [2]. This process usually lasts between 300 ms to 24 seconds
thus taking the first request longer to completed which denote as cold start,
the remainder of execution is faster and denoted as warm start [11]. FaaS
charges the user based on the cloud function’s execution duration hence it is
essential to prevent a cloud function from running infinitely. To achieve
this, all cloud platforms impose an execution timeout which is the maximum
duration a cloud function is allowed to execute. Beyond this period, the
platform will stop the execution and return a failed response. Cloud providers
allow software engineer to configure their cloud function’s execution timeout
according to their requirement. Table I summarizes the up-to-date documented
characteristics including maximum execution timeout obtained from the cloud
providers.

To minimize the overhead caused by cold start, after serving the current
traffic, cloud platforms will retain the infrastructure for a short time to
accommodate future requests. If there is no traffic within this idle period,
cloud platforms will decommission and return the computing resources for other
purposes. We refer this idle period as cloud function idle timeout. To our
knowledge, cloud providers do not officially document how long the idle
timeout lasts.

###  II-B Related Work

FaaS infrastructure retention has been studied when researchers explored FaaS’
characteristics. Lloyd et al. [4] in their study about serverless computing
reported that all FaaS VMs and containers were removed after being left idle
for 40 minutes and by using the keep-alive technique at 5-minute interval,
host VMs were recycled every 4 hours. Maissen et al. [6] described that on AWS
and IBM, it took around 10 minutes of no activity for cloud function instance
to be recycled. This period for Azure cloud function was higher at 20 minutes.

We note that previous research results have been outdated since cloud
providers regularly update their implementation. Our study extends the
previous state-of-the-art [4] and presents a method to quantify the cloud
function idle timeout. In addition, we move one step further to summarize the
evolutionary changes from 01/2020 to 01/2022. FaaS instance idle timeout and
corresponding cold start can impact the FaaS’ performance and software system,
and therefore they can be used as an input in formal models or performance
models where timing or Service Level Agreements (SLA) are a strict
requirement. Our source code is published for reproduction purposes [3].

##  III Methodology

In this section, we describe our methodology to measure function instance idle
timeout. We discuss our measurement methodology in Section III-A followed by
how we uniquely identify a function instance in Section III-B. In Section
III-C, we outline how we measure the function instance idle timeout when the
keep-alive technique is used.

###  III-A Function Idle Timeout Measurement

To measure a platform’s FaaS idle timeout, we first deployed our testing
function (discussed in Section IV-C). Next, we invoked the function
periodically with reducing interval to detect the idle timeout. We started
with a 20-minute interval because we noticed that function instances would be
decommissioned if they were left idle for this duration. Subsequently, we
decreased the interval by one minute, ran the test for five hours and checked
if the requests were served by the same instance. If all the requests were
served by different function instances, we would then proceed to the next
reduced interval. The experiments continued until we detected an interval that
made two consecutive requests served by the same instance. We noted this idle
timeout as $x$ minutes and repeated the experiment between $x$ and $(x+1)$
minutes for five hours to ensure consistent results. To detect the
evolutionary changes cloud providers implemented on function instance idle
timeout, we conducted the regular experiments over the following extended
period [12/09 - 01/10/2020], [27/03 - 13/05/2021], [19/07 - 27/07/2021] and
[08/01 - 15/01/2022].

###  III-B Function Instance Identification

To measure the idle timeout of a function instance, we measure the longest
duration that a container instance can be left idle before it is
decommissioned. This is equivalent to measuring the longest duration that
makes two consecutive requests served by the same instance. Hence, uniquely
identifying a cloud function instance is necessary. To achieve this goal, we
used the following approach:

  * •

For AWS Lambda, we obtained the “logStreamName” which is tied to the function
executing instance and extracted from the execution context.

  * •

For Azure Cloud Function, we queried the Monitoring - Log to retrieve
requests’ “customDimensions” which contained the executing instance
identifier.

  * •

For IBM Cloud Function, we extended the self-generate methodology presented by
Lloyd et al. [4] to create a universally unique identifier (UUID) for the
function instance. When a cloud function is invoked, it checks the local file
“/tmp/host.txt” for the UUID. If this file does not exist, it means this is a
new instance and a UUID is created and stored in this file. To ensure thread
safety, we implemented the synchronization with double lock mechanism while
creating and storing the UUID. When the “/tmp/host.txt’’ exists, subsequent
execution can access the file and retrieve the UUID without acquiring the lock
to prevent performance degradation.

###  III-C Function Instance Keep-Alive Idle Timeout

Once we determine the function instance idle timeout as $x$ minutes, we invoke
the function with inter-arrival request rates less than x minutes and measure
the time duration the function instance can be kept-alive. The experimental
results were to answer the question if the keep-alive technique can be used as
a work around to resolve the cold start issue. Our experiments were carried
out between [19/07 - 27/07/2021] and [08/01 - 15/01/2022].

##  IV Experimental Setup

In this section, we discuss how we setup our cloud functions on different
cloud platforms.

###  IV-A Cloud Providers

Based on Eismann et al.[12] FaaS’ use case study, we chose to evaluate FaaS on
three most popular cloud providers, namely AWS Lambda, Microsoft Azure
Function and IBM Cloud Function because they occupied the majority of FaaS use
cases (80%, 10% and 7% respectively). We did not study other providers like
Google Cloud Function, as they only occupy a small use case percentage (3%).

###  IV-B Runtime

We focused on Java in this paper because Java and Node.js are known to be the
most popular studied languages in FaaS software industry research by Scheuner
et al. [13]. Among different versions of Java, we used Java version 8 since it
is the commonly supported version on all cloud platforms.

###  IV-C Testing Function

We followed Spillner et al. [10] and Manner et al. [11] to setup a testing
function which computes the $n^{th}$ value of the Fibonacci (fib) sequence
recursively. We also used $fib(38)$ as the processing workload.

For AWS Lambda, we integrated the cloud function with API Gateway to enable
HTTPS communication. IBM and Azure Cloud Functions had this capability
supported by default hence no additional implementation was required. The
experimental system is shown in Fig. 1.

Figure 1: Experimental Setup.

We configured the AWS Lambda and IBM Cloud Function instances to have 512MB
memory and 15-second execution timeout as experimental results showed that
these configurations were appropriate for the Fibonacci task. Azure Cloud
Platform did not have memory configuration options hence we deployed our Azure
Fibonacci cloud function on a single Function App running on Linux Operating
System with 15-second execution timeout. These deployment settings help to
avoid resource-sharing which can interfere with experimental results. In
addition, for comparison purpose, we also created a Hello-World cloud function
and deployed with the same cloud instance configurations. The Hello-World
function returns a welcome message upon invocation and processes no business
logic. The cold and warm start average response times of the two experimental
cloud functions are shown in Table II.

##  V Evaluation Results

Here we present our experimental results.

Characteristics | AWS | IBM | Azure
---|---|---|---
Max Execution Timeout (mins) | 15 | 10 | 10
Max Allocated Memory (GB) | 10 | 2 | 1.5
Billing Granularity (ms) | 1 | 100 | 1
Cloud Function Idle Timeout
Cloud Function | 5 | 10 | 12
Idle Timeout (mins)
Maximum Idle Timeout | 145 | 336 | 2675
Using Keep-Alive (mins)
90-Percentile Idle Timeout | 140 | 138 | 1639
Using Keep-Alive (mins)
Evolutionary Cloud Function Idle Timeout Changes
01 - 02/2020 [acc. Maissen] | 10 | 10 | 20
09 - 10/2020 | 10 | 10 | 14
03 - 05/2021 | 5 | 10 | 12
07/2021 - 01/2022
TABLE I: Summary of FaaS Characteristics (Documented) and Cloud Function Idle Timeout And Evolutionary Changes (Undocumented) Response Time | AWS | IBM | Azure
---|---|---|---
Fibonacci (Cold start) | 1,161 | 3,169 | 2,825
Fibonacci (Warm start) | 778 | 695 | 628
Hello-World (Cold start) | 698 | 1,495 | 2,663
Hello-World (Warm start) | 79 | 169 | 81
TABLE II: Average Response Time (in ms) during Cold and Warm Start.

###  V-A Function Instance Idle Timeout

Table I shows the un-documented cloud function instance idle timeout, the
maximum and 90-percentile idle timeout when the keep-alive technique is used.
The results show that when being left idle, a cloud function instance can be
retained at most 5 minutes, 10 minutes and 12 minutes for AWS Lambda, IBM and
Azure Cloud Function, respectively. Beyond this period, cloud platforms will
reclaim the function instance and subsequent requests will encounter cold
start.

Upon completing the cloud function instance timeout on AWS Lambda and IBM
Cloud Function with 512MB allocated memory, we re-examined the experiments on
these cloud platforms with 1024MB memory to understand if there is a relation
between this timeout and the allocated memory. This additional experiment is
not applicable to Azure Cloud Function as this platform does not support
memory configuration. The results show no difference compared to results in
Table I hence we conclude that there is no relation between a cloud instance
idle timeout and allocated memory for AWS Lambda and IBM Cloud Function.

###  V-B Maximum Function Instance Idle Timeout When Using Keep-Alive
Technique

Based on the maximum idle timeout presented above, we configured our local
timer clients to poll every 5, 10 and 12 minutes for AWS Lambda, IBM and Azure
cloud functions, respectively, to examine how long the function instances can
be re-used if they are kept warm.

The results show that an AWS Lambda cloud instance can be retained at most 145
minutes. The 90-percentile for the duration of service is 140 minutes. The
small gap between the maximum and 90-percentile implies that this cloud
platform adopts a static recycling algorithm and most of the function instance
will be recycled after 140 minutes.

In contrast, IBM cloud function instance can serve a periodic traffic
continuously at most 336 minutes. Nevertheless, the 90-percentile value drops
to 138 minutes. The enormous gap between the maximum and 90-percentile may
infer that IBM cloud platform occasionally kept the cloud instance longer than
usual, however, majority of the function instances will be decommissioned
after around 138 minutes.

Microsoft Azure cloud function exhibited an interesting behavior. When tested
with the polling period between 6 to 12 minutes, a function instance can be
used at most 20 minutes. However, when we reduced the polling period to 5
minutes, we observed the function infrastructure was retained up to 44 hours
30 minutes. This behavior may induce that Azure cloud function considers the
5-minute interval as a frequent invocation pattern hence the platform keeps
the function instance warm to serve the traffic. On the contrary, a longer
period between 6 to 12 minutes may not be frequent and hence the function
instance is recycled after maximum 20 minutes.

###  V-C Function Instance Idle Timeout Evolutionary Changes

Applying our methodology at different checkpoints from 09/2020 to 01/2022, we
discovered that cloud function’s instance idle timeouts have implicitly
changed. We first noted the previous study’s result reported by Maissen et al.
[6] which were established during the [01 - 02/2020] and then we conducted
four experiments during: [09 - 10/2020], [03 - 05/2021], 07/2021 and 01/2022.
The measurement results summarized in Table I shows that IBM Cloud Function
did not change the function idle timeout since 01/2020 to 01/2022. AWS Lambda,
however, reduced this duration by 50% from 10 to 5 minutes some time between
10/2020 and 03/2021. Microsoft Azure cloud platform also shortened the
instance’s idle timeout by nearly 50% over the time. These changes were
neither documented nor communicated to software engineers.

##  VI Summary and Lessons Learnt

FaaS is designed to be ephemeral; cloud providers will decommission the cloud
function instance if it is left idle for 5 to 12 minutes depending on the
platform. Software engineers can expand the idle timeout period up to hours by
using the keep-alive technique. Nevertheless, all cloud providers will
eventually reclaim their cloud function instances regardless of active
traffic. The decision to use the keep-alive technique depends on the
application use case. For instance, if the application only serves the traffic
at certain time, software engineers may not need the keep-alive technique. If
the traffic pattern is random and there is an enormous difference between cold
and warm start like the Hello-World example, it might be helpful to apply the
keep-alive technique to reduce performance overhead. Through our experimental
results and Maissen et al. [6] study, we observed that cloud function idle
timeout has been reduced over time. These changes are not documented by cloud
providers but only reported by research studies [4], [5], [6] or by industrial
web blogs [7], [8], [9].

By knowing the cloud function instance idle timeout of each cloud platform,
software engineers can evaluate a system’s performance based on the traffic
pattern. If traffic requests arrive within the idle timeout, cold starts are
avoided and hence the requests are served with low latency. In contrast, if
the inter-arrival request rates fall beyond the cloud function idle timeout,
cold starts occur and thus function’s performance degrades. In cases where
performance guarantees are required, software engineers may consider using
keep-alive techniques or employ a cloud provider’s solution to keep the
instance warm. Examples are Provisioned Concurrency from AWS Lambda and
Dedicated or Enterprise subscription plans from Azure. These technical
solutions incur additional cost but cloud function instances are kept warm and
thus resolve the cold start issues.

##  VII Conclusion

In this paper, we presented a method to quantify the FaaS instance’s idle
timeout up to minute-accuracy. Furthermore, we also examined this idle timeout
maximum value when the keep-alive technique is used and reported the
evolutionary changes that we detected through 01/2020 - 01/2022.

In the future, we plan to evaluate actual software systems with live traffic
patterns using our knowledge of the cloud function idle timeout. This is to
determine if the reduction in cloud function idle timeout will degrade the
system’s performance. In addition, we also plan to compare the operating cost
between the two approaches: (1) using the keep-alive technique as discussed in
this paper and (2) using pre-warmed instances provided by cloud providers,
e.g., provisioned concurrency in AWS Lambda. The findings can provide software
engineers with thorough understanding about the performance and cost impact to
their systems when the cloud function idle timeout is changed on cloud
platforms.

## References

  * [1] “Building Applications with Serverless Architectures” [Online]. Available: https://aws.amazon.com/lambda/serverless-architectures-learn-more/. [Accessed: 25-Jul-2021].
  * [2] “Understanding Container Reuse in AWS Lambda.” [Online]. Available: https://aws.amazon.com/blogs/compute/container-reuse-in-lambda/. [Accessed: 25-Jul-2021].
  * [3] K. L. Ngo, “Cloud Function and Testing Client Implementation”, v1.0, Zenodo. [Online]. Available: https://doi.org/10.5281/zenodo.5722868. [Accessed: 21-Jan-2022].
  * [4] W. Lloyd, S. Ramesh, S. Chinthalapati, L. Ly, and S. Pallickara. Serverless Computing: An Investigation of Factors Influencing Microservice Performance. IEEE International Conference on Cloud Engineering (IC2E) (2018).
  * [5] W. Lloyd, M. Vu, B. Zhang, O. David and G. Leavesley, “Improving Application Migration to Serverless Computing Platforms: Latency Mitigation with Keep-Alive Workloads,” 2018 IEEE/ACM International Conference on Utility and Cloud Computing Companion (UCC Companion), 2018, pp. 195-200.
  * [6] P. Maissen, P. Felber, P. Kropf and V. Schiavoni, ”FaaSdom: A benchmark suite for serverless computing”, Proc. 14th ACM Int. Conf. Distributed Event-Based Syst. (DEBS ‘20), pp. 73-84, 2020.
  * [7] “TIL that AWS Lambda terminates instances preemptively” Xebia Blog, 29-Sep-2020. [Online]. Available: https://xebia.com/blog/til-that-aws-lambda-terminates-instances-preemptively/. [Accessed: 22-Jul-2021].
  * [8] M. Shilkov, “AWS Lambda Cold Starts After 10 Minutes”. [Online]. Available: https://mikhail.io/2019/08/aws-lambda-cold-starts-after-10-minutes/. [Accessed: 22-Jul-2021].
  * [9] E. Alliaume and B. L. Roux, “Cold start / Warm start with AWS Lambda” OCTO Talks. [Online]. Available: https://blog.octo.com/en/cold-start-warm-start-with-aws-lambda/. [Accessed: 22-Jul-2021].
  * [10] J. Spillner, C. Mateos, and D. A. Monge, “FaaSter, Better, Cheaper: The Prospect of Serverless Scientific Computing and HPC” Communications in Computer and Information Science High Performance Computing, pp. 154–168, 2017.
  * [11] J. Manner, M. Endreb, T. Heckel, and G. Wirtz, “Cold Start Influencing Factors in Function as a Service” 2018 IEEE/ACM International Conference on Utility and Cloud Computing Companion (UCC Companion), 2018.
  * [12] S. Eismann et al., A review of serverless use cases and their characteristics, Aug. 2020, [online] Available: https://bit.ly/36Ntvgy.
  * [13] J. Scheuner and P. Leitner, “Function-as-a-Service performance evaluation: A multivocal literature review” Journal of Systems and Software, vol. 170, p. 110708, 2020.


# The Change of Basis Groupoid

D.A. Wolfram  College of Engineering & Computer Science
The Australian National University, Canberra, ACT 0200
<EMAIL_ADDRESS>
###### Abstract

We show that the change of basis matrices of a set of $m$ bases of a finite
vector space is a connected groupoid of order $m^{2}$. We define a general
method to express the elements of change of basis matrices as algebraic
expressions using optimizations of evaluations of vector dot products.
Examples are given with orthogonal polynomials.

00footnotetext: MSC: Primary 15A03; Secondary 20N02, 33C45

##  1 Background and Related Work

Change of basis in a finite vector space has numerous significant and
widespread applications in scientific computing and engineering. Two
application areas are image, video and data compression [18], e.g. it can be
used to implement DCT-II in JPEG compression [14]; and improving properties of
spectral methods for solving differential equations numerically. These
properties include, better convergence [7], lower computational complexity
[10, 13], and better numerical stability [13].

Much work has been done on numerical solutions for finding the coefficients in
Legendre expansions, e.g. see the summary in Hale [8]. From equation (1.2) of
Hale and Townsend [8], these coefficients are $c_{n}^{leg}$ where

$p_{N}(x)=\sum_{n=0}^{N}c_{n}^{leg}P_{n}(x)$

and $x\in[-1,1]$. The terms $P_{n}(x)$ on the right side of the equation are
Legendre polynomials. The coefficients $c_{n}^{leg}$ are represented by
floating-point numbers. The function $p_{N}(x)$ can also be expressed using
Chebyshev polynomials of the first kind

$p_{N}(x)=\sum_{n=0}^{N}c_{n}^{cheb}T_{n}(x)$

and $x\in[-1,1]$. They provide an algorithm for implementing the transform
between the coefficients $c_{n}^{leg}$ and $c_{n}^{cheb}$ with an accuracy of
fifteen decimal places [8].

These transforms are scaled changes of bases between Legendre and Chebyshev
polynomials of the first kind. For example, let $M_{TP}$ be the change of
basis matrix from $P_{n}(x)$ to $T_{n}(x)$ where $0\leq n\leq 4$,

$M_{TP}=\begin{bmatrix}1&0&\frac{1}{4}&0&\frac{9}{64}\\\ \\\
0&1&0&\frac{3}{8}&0\\\ \\\ 0&0&\frac{3}{4}&0&\frac{5}{16}\\\ \\\
0&0&0&\frac{5}{8}&0\\\ \\\ 0&0&0&0&\frac{35}{64}\\\ \end{bmatrix}\mbox{ so
that }M_{TP}\begin{bmatrix}c_{0}^{leg}\\\ \\\ c_{1}^{leg}\\\ \\\
c_{2}^{leg}\\\ \\\ c_{3}^{leg}\\\ \\\
c_{4}^{leg}\end{bmatrix}=\begin{bmatrix}c_{0}^{cheb}\\\ \\\ c_{1}^{cheb}\\\
\\\ c_{2}^{cheb}\\\ \\\ c_{3}^{cheb}\\\ \\\ c_{4}^{cheb}\end{bmatrix}$

In this paper, we are concerned with defining algebraic expressions for the
elements in change of basis matrices, rather than numerical numerical methods
for approximating them.

For example, from Szegö [19] we can show that for the change of basis matrix
from $P_{n}(x)$ to $T_{n}(x)$, we have

$P_{n}(x)=\sum_{k=0}^{\lfloor\frac{n}{2}\rfloor}\beta(n,k)T_{n-2k}(x)$

where

$\beta(n,k)=\left\\{\begin{array}[]{ll}2^{1-2n}{{2k}\choose
k}{{2n-2k}\choose{n-k}}&\mbox{if $2k<n$}\\\ \\\
2^{-2n}{{n}\choose{\frac{n}{2}}}^{2}&\mbox{if $2k=n$}\\\ \end{array}\right.$
(1)

and $n\geq 0$. The function $\beta$ is defined by an algebraic expression and
it evaluates to the elements in the upper triangle of $M_{TP}$, e.g.
$\beta(3,1)=\frac{3}{8}$ and $\beta(4,2)=\frac{9}{64}$. There are other
equivalent expressions for $\beta$, e.g. [1, equation 22.3.13].

Apart from some specific cases such as this, there do not seem to be similar
algebraic expressions for transforms between other bases of orthogonal
polynomials, such as between Hermite polynomials and Chebyshev polynomials.

This leads to the question of finding the structure for changes of bases of a
finite-dimensional vector space. We show that this structure is a connected
groupoid [3, 4] that we call the “change of basis groupoid”.

We focus on finding the elements of the change of basis matrices for
transforms between any pair of bases for the same vector space as evaluations
of a function expressed algebraically. We call these functions “coefficient
functions”. The function $\beta$ above is an example of this.

We then consider optimizations for finding coefficient functions based on
excluding elements that are known to be zero. The first of these involves
excluding elements in the lower triangles of matrices. This occurs when the
basis polynomials have definite parity and we are only interested in even or
odd functions. This is related to the Schuster-Dilts triangular matrix
acceleration optimization that is used in representing a function with
spherical harmonics [2, §18.12.6]. Other optimizations are excluding specific
terms in basis polynomials, and excluding terms when one basis has vectors
with definite parity and the other does not. An example of this is a change of
basis between Hermite and Laguerre polynomials.

Related research has concerned defining recurrence relations for finding the
coefficients of series expansions expressed with orthogonal polynomials [12,
15].

##  2 Change of Basis is Inherent in Defining a Basis

We consider vector spaces with a basis of the form
$B=\\{s_{0},s_{1},\ldots\\}$ where each vector $v$ in the vector space can be
defined uniquely as a finite linear combination of the basis vectors, i.e.

$v=\sum_{k=0}^{n}a_{k}s_{k}$ (2)

where the $a_{k}\in\mathbb{R}$.

The coordinates of vector $v$ with respect to $B$ are another way to represent
this.

######  Definition 1.

Let $V$ be a vector space of finite dimension with coefficients over a given
field $F$, and $B=\\{v_{0},\ldots,v_{n}\\}$ be a basis of $V$. For all vectors
$v\in V$ such that $v=\sum_{k=0}^{n}a_{k}v_{k}$ where $a_{k}\in F$ and $0\leq
k\leq n$, the coordinate vector of $v$ is

$(a_{0},a_{1},\ldots,a_{n}).$

Generally, the set of basis vectors $\\{s_{0},s_{1},\ldots\\}$ is defined
using another known basis. When the vector space is $\mathbb{R}^{n}$, this is
usually the standard basis. When the vector space is the ring of polynomials
$\mathbb{R}[X]$, the basis is usually the monomials $\\{1,x,x^{2},\ldots\\}$.

######  Remark.

We assume that a basis $\\{v_{0},v_{1},\ldots,v_{n-1}\\}$ of a vector space is
an ordered basis, so that a coordinate vector of the form
$(c_{0},c_{1},\ldots,c_{n-1})$ with respect to this basis represents the
vector $c_{0}v_{0}+c_{1}v_{1}+\cdots c_{n-1}v_{n-1}$.

Defining a vector basis inherently involves defining a change of basis from a
known basis. For example, consider the vector basis of the Chebyshev
polynomials of the first kind:

$\displaystyle T_{0}(x)=$ $\displaystyle 1$ $\displaystyle T_{1}(x)=$
$\displaystyle x$ $\displaystyle T_{2}(x)=$ $\displaystyle 2x^{2}-1$
$\displaystyle T_{3}(x)=$ $\displaystyle 4x^{3}-3x$

These basis vectors are defined in terms of the monomials. In matrix form we
have a change of basis matrix from Chebyshev polynomials $T$ up to $T_{3}(x)$
to the monomials $M$ where the transposes of the coefficient vectors of the
domain basis vectors form its columns.

$\displaystyle\begin{bmatrix}1&0&-1&\phantom{-}0\\\ 0&1&\phantom{-}0&-3\\\
0&0&\phantom{-}2&\phantom{-}0\\\ 0&0&\phantom{-}0&\phantom{-}4\end{bmatrix}$

This defines a mapping from the coordinates vectors defined using the basis
$\\{T_{0}(x),\ldots,T_{3}(x)\\}$ to the coordinate vectors of the same vector
using the basis $\\{1,x,x^{2},x^{3}\\}$. For example

$\displaystyle\begin{bmatrix}1&0&-1&\phantom{-}0\\\ 0&1&\phantom{-}0&-3\\\
0&0&\phantom{-}2&\phantom{-}0\\\
0&0&\phantom{-}0&\phantom{-}4\end{bmatrix}\begin{bmatrix}\phantom{-}2\\\
\phantom{-}0\\\ -1\\\ \phantom{-}1\end{bmatrix}=\begin{bmatrix}\phantom{-}3\\\
-3\\\ -2\\\ \phantom{-}4\end{bmatrix}$

and

$T_{3}(x)-T_{2}(x)+2T_{0}(x)=4x^{3}-2x^{2}-3x+3$

so that $(2,0,-1,1)$ is mapped to $(3,-3,-2,4)$.

###  2.1 Change of Basis Matrix

In the following, we consider triangular bases of a vector space $V$. Defining
a basis $\\{s_{0},s_{1},\ldots,s_{n-1}\\}$ of $V$ involves defining a mapping
of it to another basis $\\{t_{0},t_{1},\ldots,t_{n-1}\\}$ of $V$. The standard
basis for defining a basis in $\mathbb{R}^{n}$ , or using the monomial basis
for defining a basis in $\mathbb{R}[X]$ are just two possibilities.

Instead of the monomials, we can use the shifted Legendre polynomials for
example to represent the basis of Chebyshev polynomials of the first kind. The
first four shifted Legendre polynomials represented using monomials are

$\displaystyle\tilde{P}_{0}(x)=$ $\displaystyle 1$
$\displaystyle\tilde{P}_{1}(x)=$ $\displaystyle 2x-1$
$\displaystyle\tilde{P}_{2}(x)=$ $\displaystyle 6x^{2}-6x+1$
$\displaystyle\tilde{P}_{3}(x)=$ $\displaystyle 20x^{3}-30x^{2}+12x-1.$

We express $T_{3}(x)$ uniquely in terms of the shifted Legendre polynomials by

$T_{3}(x)=\frac{1}{5}\tilde{P}_{3}(x)+\tilde{P}_{2}(x)+\frac{3}{10}\tilde{P}_{1}(x)-\frac{1}{2}\tilde{P}_{0}(x)$

and similarly for all other basis vectors in $\\{T_{0}(x),T_{1}(x),\ldots\\}$.

A change of basis matrix maps the coordinate vector of a vector $v$ defined
using the basis of Chebyshev polynomials $T$ to its coordinate vector when $v$
is defined using the basis of shifted Legendre polynomials. For example, when
$n=4$, this matrix is

$\displaystyle\begin{bmatrix}1&\frac{1}{2}&-\frac{1}{3}&-\frac{1}{2}\\\ \\\
0&\frac{1}{2}&\phantom{-}1&\phantom{-}\frac{3}{10}\\\ \\\
0&0&\phantom{-}\frac{1}{3}&\phantom{-}1\\\ \\\
0&0&\phantom{-}0&\phantom{-}\frac{1}{5}\end{bmatrix}$

##  3 Change of Basis Groupoid

Let $V$ be a vector space that has bases $s=\\{s_{0},s_{1},\ldots,s_{n}\\}$
and $t=\\{t_{0},t_{1},\ldots,t_{n}\\}$.

The following equation expresses the mapping of a change of basis matrix
$M_{ts}$.

$M_{ts}b_{s}=a_{t}$ (3)

The subscripts are simple types [5]. The columns of $M_{ts}$ are the
transposed coordinate vectors with respect to $t$ of the basis vectors of $s$.

######  Lemma 1.

For every change of basis matrix $M_{ts}$, its inverse $M_{ts}^{-1}$ exists
and $M_{ts}^{-1}=M_{st}$.

###### Proof.

$M_{ts}$ is a square matrix whose columns are the transposed coordinate
vectors with respect to $t$ of the basis vectors of $s$ . These columns are
linearly independent, so that $M_{ts}$ is invertible by the Fundamental
Theorem of Invertible Matrices, e.g [16, Theorem 3.27].

To show $M_{ts}^{-1}=M_{st}$, consider any column matrices $a$ and $b$ such
that $M_{ts}b=a$.

Now $M_{ts}^{-1}M_{st}b=M_{ts}^{-1}a$. It follows that $M_{ts}^{-1}a=b$ by the
associativity of matrix multiplication. If $a$ is known then $M_{ts}^{-1}$ is
the matrix that can be similarly used to find $b$, as required. ∎

######  Definition 2.

Two change of basis matrices $M_{ts}$ and $M_{vu}$ are equal if and only if
they have the same elements, $t=v$ and $s=u$.

######  Lemma 2.

Every change of basis matrix is unique.

###### Proof.

Suppose $M=M_{ts}$ is a change of basis matrix. If $M$ is not unique, there is
a change of basis matrix $N=N_{ts}$ that has the same dimensions as $M$ and
$M\not=N$. The matrix $M^{-1}$ exists from Lemma 1, and $N$ is its right
inverse. We have $M=M(M^{-1}N)$ and $M(M^{-1}N)=(MM^{-1})N$, so that $M=N$
which is a contradiction that they are unequal. ∎

######  Theorem 1.

Let $V$ be a vector space and suppose there is a set $S$ of $m$ bases of $V$.
The set of change of basis matrices $M_{ts}$ where $s,t\in S$ is a connected
groupoid $G$ of order $m^{2}$.

###### Proof.

The axioms of the algebraic definition of a groupoid [3, 4] are met, i.e.

  * •

The elements of $G$ are the change of basis matrices and the identity matrices
$M_{tt}$ where $t\in S$ and they all have the same dimensions.

  * •

There is a partially defined associative binary operation $\circ$ on the
elements of $G$. For every $M,N\in G$, the operation $\circ$ is defined if and
only if $M$ has the form $M_{ut}$, and $N$ has the form $N_{ts}$ in which case
$M\circ N=M_{us}\in G$. The operation $\circ$ is matrix multiplication and we
omit the symbol.

  * •

If $M=M_{ts}$ is any element of the groupoid, then its inverse $M^{-1}=M_{st}$
is an element of the groupoid and it is defined by matrix inversion of $M$
following Lemma 1.

  * •

If $M=M_{ts}$ is any element of the groupoid, then $MM^{-1}=M_{tt}$ is an
identity element of the groupoid.

The groupoid is connected or transitive, because for any two bases $s$ and $t$
in $S$, there exists a matrix $M_{ts}\in G$.

For each of the $m$ bases there are $m^{2}$ permutations of them taken two at
a time with repetitions, which is the order of the groupoid following Lemma 2.
∎

###  3.1 Example

The set $S$ comprises the three bases: monomials $M$; Legendre polynomials $P$
expressed in terns of monomials; and Chebyshev polynomials of the first kind
$T$ expressed in terns of monomials. All basis vectors have even degree from
$0$ to $6$. The change of basis matrix

$M_{TP}=\begin{bmatrix}1&\frac{1}{4}&\frac{9}{64}&\frac{25}{256}\\\ \\\
0&\frac{3}{4}&\frac{5}{16}&\frac{105}{512}\\\ \\\
0&0&\frac{35}{64}&\frac{63}{256}\\\ \\\ 0&0&0&\frac{231}{512}\end{bmatrix}$

This gives

$\begin{bmatrix}1&\frac{1}{4}&\frac{9}{64}&\frac{25}{256}\\\ \\\
0&\frac{3}{4}&\frac{5}{16}&\frac{105}{512}\\\ \\\
0&0&\frac{35}{64}&\frac{63}{256}\\\ \\\
0&0&0&\frac{231}{512}\end{bmatrix}\begin{bmatrix}0\\\ \\\ 1\\\ \\\ 0\\\ \\\
2\end{bmatrix}=\begin{bmatrix}\frac{57}{128}\\\ \\\ \frac{297}{256}\\\ \\\
\frac{63}{128}\\\ \\\ \frac{231}{256}\end{bmatrix}$

In terms of polynomials, we have

$\displaystyle 2P_{6}(x)+P_{2}(x)$
$\displaystyle=\frac{231}{256}T_{6}(x)+\frac{63}{128}T_{4}(x)+\frac{297}{256}T_{2}(x)+\frac{57}{128}T_{0}(x)$
$\displaystyle=\frac{1}{8}(231x^{6}-315x^{4}+117x^{2}-9).$

From Boyd [2], the matrix

$M_{PT}=\begin{bmatrix}1&-\frac{1}{3}&-\frac{1}{15}&-\frac{1}{35}\\\ \\\
0&\frac{4}{3}&-\frac{16}{21}&-\frac{4}{21}\\\ \\\
0&0&\frac{64}{35}&-\frac{384}{385}\\\ \\\ 0&0&0&\frac{512}{231}\end{bmatrix}$

which is the inverse of $M_{TP}$. The matrix $M_{MP}$ is

$\begin{bmatrix}1&-\frac{1}{2}&\frac{3}{8}&-\frac{5}{16}\\\ \\\
0&\frac{3}{2}&-\frac{15}{4}&\frac{105}{16}\\\ \\\
0&0&\frac{35}{8}&-\frac{315}{16}\\\ \\\ 0&0&0&\frac{231}{16}\end{bmatrix}$

From these we can find the other groupoid elements, $M_{PM}$,
$M_{TM}=M_{TP}M_{PM}$, $M_{MT}$, $I_{MM}$, $I_{PP}$ and $I_{TT}$. There are
$m^{2}=9$ elements in total. There are three identity matrices, but they are
unequal because of their types.

###  3.2 The Exchange Basis

######  Definition 3.

Given two change of basis mappings ${\cal T}_{2}:c\rightarrow b$ and ${\cal
T}_{1}:b\rightarrow d$, the exchange basis is $b$.

Suppose that we wish to find $\alpha_{3}$ for a pair of bases $s$ and $t$ of a
subspace of $\mathbb{R}[X]$. It is convenient to use the monomials $M$ as the
exchange basis because $\alpha$ is sometimes known in the literature [1, 9,
11] for ${\cal T}_{2}:s\rightarrow M$ and ${\cal T}_{1}:M\rightarrow t$.

##  4 Optimizing with the Triangular Basis

From the change of basis groupoid, given two change of basis matrices
$M_{cb}M_{bd}$ the elements of $M_{cd}$ are formed from the vector dot
products of the rows of $M_{cb}$ and the columns of $M_{bd}$. Bases that
satisfy the following condition lead to an optimization of these vector dot
products.

######  Definition 4.

Let $V$ be a vector space of finite dimension $n>0$ and $B_{1}$ and $B_{2}$ be
bases of $V$.

The basis $B_{2}$ is a triangular basis with respect to $B_{1}$ if and only if
there is a permutation $\\{v_{1},\ldots,v_{n}\\}$ of the coordinate vectors of
$B_{2}$ with respect to $B_{1}$ such that the $n\times n$ matrix
$\left[v_{1}^{T},\ldots,v_{n}^{T}\right]$ is an upper triangular matrix.

An example of an orthogonal basis in $\mathbb{R}^{8}$ that is not a triangular
basis is the Haar function wavelet matrix [18]:

$\displaystyle
W_{8}=\begin{bmatrix}1&\phantom{-}1&\phantom{-}1&\phantom{-}0&\phantom{-}1&\phantom{-}0&\phantom{-}0&\phantom{-}0\\\
1&\phantom{-}1&\phantom{-}1&\phantom{-}0&-1&\phantom{-}0&\phantom{-}0&\phantom{-}0\\\
1&\phantom{-}1&-1&\phantom{-}0&\phantom{-}0&\phantom{-}1&\phantom{-}0&\phantom{-}0\\\
1&\phantom{-}1&-1&\phantom{-}0&\phantom{-}0&-1&\phantom{-}0&\phantom{-}0\\\
1&-1&\phantom{-}0&\phantom{-}1&\phantom{-}0&\phantom{-}0&\phantom{-}1&\phantom{-}0\\\
1&-1&\phantom{-}0&\phantom{-}1&\phantom{-}0&\phantom{-}0&-1&\phantom{-}0\\\
1&-1&\phantom{-}0&-1&\phantom{-}0&\phantom{-}0&\phantom{-}0&\phantom{-}1\\\
1&-1&\phantom{-}0&-1&\phantom{-}0&\phantom{-}0&\phantom{-}0&-1\end{bmatrix}$

The basis vectors $(1,1,1,1,1,1,1,1)$ and $(1,1,1,1,-1,-1,-1,-1)$ with respect
to the standard basis both have non-zero coordinates in the eight dimension.

An example of a triangular basis is Chebyshev polynomials of the first kind of
odd degree up to degree $5$. This basis is

$\\{x,\ \ 4x^{3}-3x,\ \ 16x^{5}-20x^{3}+5x\\}$

The basis vectors of this subspace of $\mathbb{R}[X]$ have the following
coordinate vectors wth respect to the basis $\\{x,x^{3},x^{5}\\}$:

$(1,0,0),\ \ (-3,4,0),\ \ (5,-20,16)$

and the matrix

$\displaystyle\begin{bmatrix}1&-3&\phantom{-}5\\\ 0&\phantom{-}4&-20\\\
0&\phantom{-}0&\phantom{-}16\end{bmatrix}$

is an upper triangular matrix.

This optimization is related to the Schuster-Dilts triangular matrix
acceleration optimization. It was found independently by Schuster [17] and
Dilts [6]. Boyd [2, §18.12.6] gives an example of it involving a change of
basis from $T_{n}(x)$ to $P_{n}(x)$ where they have even parity.

By excluding elements below the main diagonal, a $m\times m$ matrix can be
represented with $\frac{1}{2}(m^{2}+m)$ elements.

##  5 The Dot Product Solution Method

We consider a method of defining algebraically a change of basis function
between two triangular bases of a vector space. The method uses the matrix dot
product of change of basis matrices.

######  Definition 5.

Suppose that $s$ and $t$ are triangular bases of a vector space $V$. The
mapping $\mathcal{T}:s\rightarrow t$ satisfies

$s_{n}=\sum_{k=0}^{n}\alpha(n,k)t_{n-k}$ (4)

where $\alpha(n,k)\in\mathbb{R}$, i.e. each basis vector of $s$ is a unique
linear combination of the basis vectors of $t$. The function $\alpha$ is
called a coefficient function.

There is a change of basis matrix equation from equation (4):

$\displaystyle\begin{bmatrix}\vdots&\cdots&\vdots&\vdots&\vdots\\\
0&\cdots&\alpha(n-3,0)&\alpha(n-2,1)&\alpha(n-1,2)&\alpha(n,3)\\\
0&\cdots&0&\alpha(n-2,0)&\alpha(n-1,1)&\alpha(n,2)\\\
0&\cdots&0&0&\alpha(n-1,0)&\alpha(n,1)\\\
0&\cdots&0&0&0&\alpha(n,0)\end{bmatrix}\begin{bmatrix}\vdots\\\ b_{3}\\\
b_{2}\\\ b_{1}\\\ b_{0}\end{bmatrix}=\begin{bmatrix}\vdots\\\ a_{3}\\\
a_{2}\\\ a_{1}\\\ a_{0}\end{bmatrix}$

The matrix on the left is a square matrix. This represents a function that
maps a a matrix of coordinates of a vector in the domain basis $s$ in the
second matrix to the last matrix which is the coordinates of the same vector
in the range basis $t$. Given a change of basis mapping that satisfies
equation (4), a solution method is a method to find algebraic expressions for
the coefficient function $\alpha(n,k)$.

For example, when $n=6$, $M_{ts}$ is a $7\times 7$ matrix. When it is applied
to the coordinate matrix for $s_{3}(x)$

$\displaystyle M_{ts}\begin{bmatrix}0\\\ 0\\\ 0\\\ 1\\\ 0\\\ 0\\\ 0\\\
\end{bmatrix}=\begin{bmatrix}\alpha(3,3)\\\ \alpha(3,2)\\\ \alpha(3,1)\\\
\alpha(3,0)\\\ 0\\\ 0\\\ 0\\\ \end{bmatrix}$

it produces the fourth column of $M_{ts}$ that has the following coordinates
of $s_{3}(x)$ in the basis $t$:
$(\alpha(3,3),\alpha(3,2),\alpha(3,1),\alpha(3,0),0,0,0)$. From equation 4, we
have

$s_{3}(x)=\sum_{k=0}^{3}\alpha(3,k)t_{3-k}(x).$

Given two change of basis matrices of the same dimensions, $M_{ts}$ and
$M_{sv}$ we have $M_{tv}=M_{ts}M_{sv}$ from Lemma 1.

More specifically, if the elements in $M_{ts}$ are applications of
$\alpha_{1}$ and those of $M_{sv}$ are $\alpha_{2}$, then we can find the
elements that are applications of $\alpha_{3}$ in $M_{tv}$ by matrix
multiplication

The leftmost matrix is a square upper triangular matrix with $n+1$ rows and
columns. The expression for $\alpha_{3}$ is found from the dot product of the
$i$th row of $M_{ts}$ with the $j$th column of $M_{sv}$. Given such a $h\times
h$ matrix $M$, we can show that the entry $M_{i,j}=\alpha(n-(h-j),j-i)$ where
$1\leq i,j\leq h$ and $j\geq i$. We use the convention that the sum below
equals $0$ when $i>j$.

$\alpha_{3}(n-(h-j),j-i)=\sum_{v=i}^{j}\alpha_{1}(n-(h-v),v-i)\alpha_{2}(n-(h-j),j-v)$
(5)

The entry for $\alpha(m,k)$ is in row $m-n+h-k$ and column $m-n+h$ where
$0\leq k\leq m$ and $n-h+1\leq m\leq n$.

It is convenient to consider the dot product with the last column of $M_{sv}$
when $j=h$. The matrix equation then has the following form.

$\displaystyle\begin{bmatrix}\vdots&\vdots&\vdots&\vdots&\vdots\\\
0&\alpha_{1}(n-3,0)&\alpha_{1}(n-2,1)&\alpha_{1}(n-1,2)&\alpha_{1}(n,3)\\\
0&0&\alpha_{1}(n-2,0)&\alpha_{1}(n-1,1)&\alpha_{1}(n,2)\\\
0&0&0&\alpha_{1}(n-1,0)&\alpha_{1}(n,1)\\\
0&0&0&0&\alpha_{1}(n,0)\end{bmatrix}\begin{bmatrix}\vdots\\\
\alpha_{2}(n,3)\\\ \alpha_{2}(n,2)\\\ \alpha_{2}(n,1)\\\
\alpha_{2}(n,0)\end{bmatrix}=\begin{bmatrix}\vdots\\\ \alpha_{3}(n,3)\\\
\alpha_{3}(n,2)\\\ \alpha_{3}(n,1)\\\ \alpha_{3}(n,0)\end{bmatrix}$

Equation (5) simplifies to

$\alpha_{3}(n,k)=\sum_{v=0}^{k}\alpha_{1}(n-v,k-v)\alpha_{2}(n,v)$ (6)

where $0\leq k\leq n$, which provides a solution.

###  5.1 Further Optimizations

The evaluation of $\alpha_{3}(n,k)$ in equation (6) can be optimized when
there are values of $\alpha_{1}(n-v,k-v)$ or $\alpha_{2}(n,v)$ that can be
excluded. For example, Chebyshev polynomials of the first kind $T_{n}(x)$ have
definite parity [2, Definition 21, §8.2]. The change of basis matrix of them
up to order $4$ with respect to the monomials is

$\displaystyle M_{MT}=\begin{bmatrix}1&0&-1&\phantom{-}0&\phantom{-}1\\\
0&1&\phantom{-}0&-3&\phantom{-}0\\\ 0&0&\phantom{-}2&\phantom{-}0&-8\\\
0&0&\phantom{-}0&\phantom{-}4&\phantom{-}0\\\
0&0&\phantom{-}0&\phantom{-}0&\phantom{-}8\end{bmatrix}$

In terms of the rows above the main diagonal, an element $m_{i,j}$ of this
matrix will be $0$ when $j-i$ is odd and $j\geq i$ where $1\leq i,j,\leq 5$.
For the columns, we may only be interested in basis polynomials that all have
even degree, or odd degree. In this example, Chebyshev polynomials of the
first kind of even degree span the same subspace as $\\{1,x^{2},x^{4}\\}$ and
those of odd degree span the same subspace as $\\{x,x^{3}\\}$.

If the change of basis just involves Chebyshev polynomials of the first kind
of even degree, the following compressed matrix can suffice.

$\displaystyle\begin{bmatrix}1&-1&\phantom{-}1\\\ 0&\phantom{-}2&-8\\\
0&\phantom{-}0&\phantom{-}8\end{bmatrix}$

and similarly for those of odd degree:

$\displaystyle\begin{bmatrix}1&-3\\\ 0&\phantom{-}4\\\ \end{bmatrix}$

Another compression of a change of basis matrix expressed using the monomials
occurs when vectors of degree less than a fixed number $k$ are omitted. For
example, with $M_{MT}$ we may want to exclude the vectors $1$ and $x$ from the
basis $\\{1,x,x^{2},x^{3}x^{4}\\}$, i.e. $k=1$. We can use the following
change of basis matrix instead of $M_{MT}$.

$\displaystyle\begin{bmatrix}2&0&-8\\\ 0&4&\phantom{-}0\\\
0&0&\phantom{-}8\end{bmatrix}$

Combinations of these can be used too, e.g. Chebyshev polynomials of even
degree excluding terms of degree less than $2$, which has basis in the
monomials of $\\{x^{2},x^{4}\\}$, and change of basis matrix

$\displaystyle\begin{bmatrix}2&-8\\\ 0&\phantom{-}8\end{bmatrix}$

Equation (6) is an optimization for finding the last column of a $m\times m$
matrix $M_{tv}=M_{ts}M_{sv}$ where $s,t$ and $v$ are triangular bases of the
same vector space. The elements below the main diagonal are excluded. We now
consider four specific further optimizations of equation (6) when other
elements of the matrices can be excluded. These cases are:

  1. 1.

Exclude the first $k_{1}$ rows and first $k_{1}$ columns

  2. 2.

Exclude the last $k_{2}$ rows and last $k_{2}$ columns

  3. 3.

Exclude elements $m_{i,j}$ where $j-i$ is odd, $1\leq i,j\leq m$ and $j\geq i$

  4. 4.

Exclude elements $m_{i,j}$ where $1\leq i,j\leq m$, $m$ is odd and either $i$
or $j$ is even.

An upper triangular $m\times m$ matrix can be represented with
$\frac{1}{2}(m^{2}+m)$ elements. The four optimizations above further reduce
the number of elements required. The number of elements that are included are,
respectively:

$\displaystyle\>\>\>\>\>\>\>\frac{1}{2}((m-k_{1})^{2}+(m-k_{1}))$ (7)
$\displaystyle\>\>\>\>\>\>\>\frac{1}{2}((m-k_{2})^{2}+(m-k_{2}))$ (8)
$\displaystyle\left\\{\begin{array}[]{ll}\frac{1}{4}m(m+2)&\mbox{if $m$ is
even}\\\ \\\ \frac{1}{4}(m+1)^{2}&\mbox{if if $m$ is odd}\\\
\end{array}\right.$ (12)
$\displaystyle\left\\{\begin{array}[]{ll}\frac{1}{8}m(m+2)&\mbox{if $m$ is
even}\\\ \\\ \frac{1}{8}(m+1)(m+3)&\mbox{if if $m$ is odd}\\\
\end{array}\right.$ (16)

The last two expressions for the included elements can be shown by
mathematical induction.

In equations (17) to (19) below, the coefficient functions are with respect to
the original $m\times m$ matrices. In terms of bases, examples of these
optimizations occur when changing bases between classical orthogonal
polynomials. Case 1 involves omitting the terms of $t$ and $v$ of degree not
exceeding $k_{1}-1$. Case 2 occurs when omitting terms of $t$ and $v$ of
degree at least $m-k_{2}$ When at least one of $t$ and $v$ has polynomials of
definite parity and includes all polynomials of degree less than $m$ then case
3 applies. Case 4 occurs when both $t$ and $v$ have definite parity and we are
interested only in polynomials either of even or odd degree.

For cases 1 and 2 we have

$\alpha_{3}(n,k)=\sum_{v=0}^{k}\alpha_{1}(n-v,k-v)\alpha_{2}(n,v)$ (17)

where $n=m-k_{2}-1$ and $0\leq k\leq n-k_{1}$.

In case 3, the dimensions of the matrices are not decreased. We have

$\alpha_{3}(n,k)=\sum^{k}_{\mathclap{\begin{subarray}{c}v=0\\\
k-v\mbox{\small\; even}\end{subarray}}}\alpha_{1}(n-v,k-v)\alpha_{2}(n,v)$
(18)

where $n=m-1$ and $0\leq k\leq n$.

In case 4, we can assume that $m$ is odd without loss of generality.
Otherwise, if $m$ is even, the first column would be excluded and the first
row would alternate between excluded elements and $0$. It follows that the
first row can also be excluded, which is case 1, above with $k_{1}=1$.

The dimensions of $M_{ts}$ after elements are excluded is
$\lceil\frac{m}{2}\rceil$.

$\alpha_{3}(n,k)=\sum_{v=0}^{k}\alpha_{1}(n-2v,2(k-v))\alpha_{2}(n,2v)$ (19)

where $n=m-1$ and $0\leq k\leq\frac{n}{2}$.

We can express equation (19) using coefficient functions for the matrices with
excluded elements.

######  Definition 6.

$\beta(n,k)=\alpha(n,2k)$ (20)

where $0\leq k\leq\lfloor\frac{n}{2}\rfloor$.

We then obtain equation (6) with respect to the matrices with excluded
elements:

$\beta_{3}(n,k)=\sum_{v=0}^{k}\beta_{1}(n-2v,k-v)\beta_{2}(n,v)$

where $0\leq k\leq\frac{n}{2}$.

For example, given

$\displaystyle\begin{bmatrix}\vdots&\cdots&\vdots&\vdots&\vdots&\vdots&\vdots\\\
0&\cdots&\alpha_{1}(n-4,0)&\alpha_{1}(n-3,1)&\alpha_{1}(n-2,2)&\alpha_{1}(n-1,3)&\alpha_{1}(n,4)\\\
0&\cdots&0&\alpha_{1}(n-3,0)&\alpha_{1}(n-2,1)&\alpha_{1}(n-1,2)&\alpha_{1}(n,3)\\\
0&\cdots&0&0&\alpha_{1}(n-2,0)&\alpha_{1}(n-1,1)&\alpha_{1}(n,2)\\\
0&\cdots&0&0&0&\alpha_{1}(n-1,0)&\alpha_{1}(n,1)\\\
0&\cdots&0&0&0&0&\alpha_{1}(n,0)\end{bmatrix}\begin{bmatrix}\vdots\\\
\alpha_{2}(n,4)\\\ \alpha_{2}(n,3)\\\ \alpha_{2}(n,2)\\\ \alpha_{2}(n,1)\\\
\alpha_{2}(n,0)\end{bmatrix}$

and $n=8$, suppose $k=2$, so that

$\displaystyle\alpha_{3}(8,4)=$
$\displaystyle\alpha_{1}(8,4)\alpha_{2}(8,0)+\alpha_{1}(6,2)\alpha_{2}(8,2)+\alpha_{1}(4,0)\alpha_{2}(8,4)$

with respect to the matrices with excluded elements

$\displaystyle\begin{bmatrix}\vdots&\cdots&\vdots&\vdots&\vdots\\\
0&\cdots&\alpha_{1}(n-4,0)&\alpha_{1}(n-2,2)&\alpha_{1}(n,4)\\\
0&\cdots&0&\alpha_{1}(n-2,0)&\alpha_{1}(n,2)\\\
0&\cdots&0&0&\alpha_{1}(n,0)\end{bmatrix}\begin{bmatrix}\vdots\\\
\alpha_{2}(n,4)\\\ \alpha_{2}(n,2)\\\ \alpha_{2}(n,0)\end{bmatrix}$

This gives

$\beta_{3}(8,2)=\beta_{1}(8,2)\beta_{2}(8,0)+\beta_{1}(6,1)\beta_{2}(8,1)+\beta_{1}(4,0)\beta_{2}(8,2),$

which is the dot product with respect to the coefficient functions
$\beta_{1}(x,v)$ and $\beta_{2}(x,v)$ by applying equation (20):

$\displaystyle\begin{bmatrix}\vdots&\cdots&\vdots&\vdots&\vdots\\\
0&\cdots&\beta_{1}(n-4,0)&\beta_{1}(n-2,1)&\beta_{1}(n,2)\\\
0&\cdots&0&\beta_{1}(n-2,0)&\beta_{1}(n,1)\\\
0&\cdots&0&0&\beta_{1}(n,0)\end{bmatrix}\begin{bmatrix}\vdots\\\
\beta_{2}(n,2)\\\ \beta_{2}(n,1)\\\ \beta_{2}(n,0)\end{bmatrix}$

##  6 Examples with Orthogonal Polynomials

Definitions of the the classical orthogonal polynomials are given in
Koornwinder et al. [9, §18.3]. Three of these kinds of orthogonal polynomials
are Chebyshev Polynomials of the first kind, $T_{n}(x)$, Laguerre polynomials
$L_{n}(x)$, and Physicist’s Hermite polynomials $H_{n}(x)$. There do not
appear to be results on changing basis from Laguerre or Hermite polynomials to
Chebyshev polynomials of the first kind.

The polynomials $T_{n}(x)$ and $H_{n}(x)$ have definite parity [2, Definition
21, §8.2], and the Laguerre polynomials $L_{n}(x)$ do not have definite
parity. $T_{n}(x)$ $L_{n}(x)$ and $H_{n}(x)$ all have degree $n$ where $n\geq
0$.

###  6.1 Example of Case 3

If we want to change basis from the Laguerre polynomials up to degree $5$ to
Chebyshev polynomials of the first kind, we can use the change of basis
equation $M_{TL}=M_{TM}M_{ML}$ where

$M_{TM}=$ $\left[\begin{array}[]{cccccccc}1&0&\frac{1}{2}&0&\frac{3}{8}&0\\\
0&1&0&\frac{3}{4}&0&\frac{5}{8}\\\ 0&0&\frac{1}{2}&0&\frac{1}{2}&0\\\
0&0&0&\frac{1}{4}&0&\frac{5}{16}\\\ 0&0&0&0&\frac{1}{8}&0\\\
0&0&0&0&0&\frac{1}{16}\\\ \end{array}\right]$

and $M_{ML}=$
$\left[\begin{array}[]{cccccccc}1&\phantom{-}1&\phantom{-}1&\phantom{-}1&\phantom{-}1&\phantom{-}1\\\
0&-1&-2&-3&-4&-5\\\
0&\phantom{-}0&\phantom{-}\frac{1}{2}&\phantom{-}\frac{3}{2}&\phantom{-}3&\phantom{-}5\\\
0&\phantom{-}0&\phantom{-}0&-\frac{1}{6}&-\frac{2}{3}&-\frac{5}{3}\\\
0&\phantom{-}0&\phantom{-}0&\phantom{-}0&\phantom{-}\frac{1}{24}&\phantom{-}\frac{5}{24}\\\
0&\phantom{-}0&\phantom{-}0&\phantom{-}0&\phantom{-}0&-\frac{1}{120}\\\
\end{array}\right]$

The product is

$M_{TL}=$
$\left[\begin{array}[]{cccccccc}1&\phantom{-}1&\phantom{-}\frac{5}{4}&\phantom{-}\frac{7}{4}&\phantom{-}\frac{161}{64}&\phantom{-}\frac{229}{64}\\\
0&-1&-2&-\frac{25}{8}&-\frac{9}{2}&-\frac{1201}{192}\\\
0&\phantom{-}0&\phantom{-}\frac{1}{4}&\phantom{-}\frac{3}{4}&\phantom{-}\frac{73}{48}&\phantom{-}\frac{125}{48}\\\
0&\phantom{-}0&\phantom{-}0&-\frac{1}{24}&-\frac{1}{6}&-\frac{161}{384}\\\
0&\phantom{-}0&\phantom{-}0&\phantom{-}0&\phantom{-}\frac{1}{192}&\phantom{-}\frac{5}{192}\\\
0&\phantom{-}0&\phantom{-}0&\phantom{-}0&\phantom{-}0&-\frac{1}{1920}\\\
\end{array}\right]$

and, for example, from the fifth column, we have

$\displaystyle L_{4}(x)=$
$\displaystyle\frac{1}{192}T_{4}(x)-\frac{1}{6}T_{3}(x)+\frac{73}{48}T_{2}(x)-\frac{9}{2}T_{1}(x)+\frac{161}{64}T_{0}(x)$
$\displaystyle=$ $\displaystyle\frac{x^{4}}{24}-\frac{2x^{3}}{3}+3x^{2}-4x+1$

Since $L_{n}(x)$ is not definite and $T_{n}(x)$ we can only exclude the
elements that are zero in the upper triangle of $M_{TM}$ in finding
$\alpha_{3}(n,k)$. The dimensions of the matrices are unchanged.

From Mason and Handscomb [11, equation (2.14)], and equivalently Tao [20]

$x^{n}=2^{1-n}{\sum_{k=0}^{\lfloor\frac{n}{2}\rfloor}}{}^{{}^{\prime}}{{n}\choose{k}}T_{n-2k}(x)$
(21)

where the primed sum means that its $k$th term is halved if $n$ is even and
$k=\frac{n}{2}$.

We have

$\alpha_{1}(n,k)=\left\\{\begin{array}[]{ll}2^{1-n}{n\choose{k/2}}&\mbox{if
$k$ is even and $k\not=n$}\\\ 2^{-n}{n\choose{k/2}}&\mbox{if $k$ is even and
$k=n$}\\\ 0&\mbox{if $k$ is odd.}\end{array}\right.$

where $0\leq k\leq n$.

From equation 18.5.12 of Koornwinder et al. [9] for the generalized Laguerre
polynomials

$L_{n}^{(\alpha)}(x)=\sum_{l=0}^{n}\frac{(\alpha+l+1)_{n-l}}{(n-l)!\;l!}(-x)^{l}$

so that a change of basis matrix from the Laguerre polynomials to the
monomials has the coefficient function

$\alpha_{2}(n,k)=(-1)^{n-k}\frac{(n-k+1)_{k}}{k!\;(n-k)!}$

where $(n-k+1)_{k}$ is an application of the Pochhammer symbol or rising
factorial.

Applying case 3, gives from equation (18),

$\alpha_{3}(n,k)=\sum^{k}_{\mathclap{\begin{subarray}{c}v=0\\\
k-v\mbox{\small\; even}\end{subarray}}}\alpha_{1}(n-v,k-v)\alpha_{2}(n,v)$

where $0\leq k\leq n$.

We have

$L_{n}(x)=\sum_{v=0}^{n}\alpha_{3}(n,v)T_{n-v}(x)$

where $0\leq k\leq n$. From equation (12), the number of included elements is
$\frac{1}{4}(6\times 8)=12$ which can also be seen from $M_{TM}$.

###  6.2 Example of Cases 1 and 4

Suppose that we want to change basis from Physicist’s Hermite polynomials of
degree up to $7$ to Chebyshev polynomials of the first kind. A change of basis
equation is $M_{TH}=M_{TM}M_{MH}$ where

$M_{TM}=$
$\left[\begin{array}[]{cccccccc}1&0&\frac{1}{2}&0&\frac{3}{8}&0&\frac{5}{16}&0\\\
0&1&0&\frac{3}{4}&0&\frac{5}{8}&0&\frac{35}{64}\\\
0&0&\frac{1}{2}&0&\frac{1}{2}&0&\frac{15}{32}&0\\\
0&0&0&\frac{1}{4}&0&\frac{5}{16}&0&\frac{21}{64}\\\
0&0&0&0&\frac{1}{8}&0&\frac{3}{16}&0\\\
0&0&0&0&0&\frac{1}{16}&0&\frac{7}{64}\\\ 0&0&0&0&0&0&\frac{1}{32}&0\\\
0&0&0&0&0&0&0&\frac{1}{64}\\\ \end{array}\right]$

and $M_{MH}=$ $\left[\begin{array}[]{cccccccc}1&0&-2&0&12&0&-120&0\\\
0&2&0&-12&0&120&0&-1680\\\ 0&0&4&0&-48&0&720&0\\\ 0&0&0&8&0&-160&0&3360\\\
0&0&0&0&16&0&-480&0\\\ 0&0&0&0&0&32&0&-1344\\\ 0&0&0&0&0&0&64&0\\\
0&0&0&0&0&0&0&128\\\ \end{array}\right]$

If we want to change basis for polynomials of odd degree, this is an example
of cases 1 and 4 in §5.1. The first column of $M_{TM}$ can be excluded because
it corresponds to the representation of monomial $1$ which has even degree.
The first row can also be excluded because the non-zero elements are
coefficients of $T_{0}(x)$ in the respective representations of
$\\{x,x^{2},\ldots,x^{7}\\}$, and $T_{0}(x)$ has even parity.

Excluding the first rows and columns gives the following $7\times 7$ matrices,
respectively.

$\left[\begin{array}[]{cccccccc}1&0&\frac{3}{4}&0&\frac{5}{8}&0&\frac{35}{64}\\\
0&\frac{1}{2}&0&\frac{1}{2}&0&\frac{15}{32}&0\\\
0&0&\frac{1}{4}&0&\frac{5}{16}&0&\frac{21}{64}\\\
0&0&0&\frac{1}{8}&0&\frac{3}{16}&0\\\ 0&0&0&0&\frac{1}{16}&0&\frac{7}{64}\\\
0&0&0&0&0&\frac{1}{32}&0\\\ 0&0&0&0&0&0&\frac{1}{64}\\\ \end{array}\right]$

$\left[\begin{array}[]{cccccccc}2&0&-12&0&120&0&-1680\\\ 0&4&0&-48&0&720&0\\\
0&0&8&0&-160&0&3360\\\ 0&0&0&16&0&-480&0\\\ 0&0&0&0&32&0&-1344\\\
0&0&0&0&0&64&0\\\ 0&0&0&0&0&0&128\\\ \end{array}\right]$

From equation (7), this results in $\frac{1}{2}(7^{2}+7)=28$ elements in the
upper triangles of these matrices. By applying equation (17), we have
$k_{1}=1$, $k_{2}=0$, $m=8$, $n=7$ and $0\leq k\leq 6$, so that

$\alpha_{3}(7,k)=\sum_{v=0}^{k}\alpha_{1}(7-v,k-v)\alpha_{2}(7,v).$

We have, for example,

$\displaystyle\alpha_{3}(7,3)=$
$\displaystyle\alpha_{1}(7,3)\alpha_{2}(7,0)+\alpha_{1}(6,2)\alpha_{2}(7,1)+\alpha_{1}(5,1)\alpha_{2}(7,2)+\alpha_{1}(4,0)\alpha_{2}(7,3)$
$\displaystyle=$ $\displaystyle 0\times\alpha_{2}(7,0)+\alpha_{1}(6,2)\times
0+0\times\alpha_{2}(7,2)+\alpha_{1}(4,0)\times 0$ $\displaystyle=$
$\displaystyle 0$

and

$\displaystyle\alpha_{3}(7,2)=$
$\displaystyle\alpha_{1}(7,2)\alpha_{2}(7,0)+\alpha_{1}(6,1)\alpha_{2}(7,1)+\alpha_{1}(5,0)\alpha_{2}(7,2)$
$\displaystyle=$ $\displaystyle\frac{7}{64}\times 128+0\times
0+\frac{1}{16}\times-1344$ $\displaystyle=$ $\displaystyle-70$

The elements of the matrices that are zero are known from the outset.

The result of applying case 4 is to exclude these elements. In the resulting
$7\times 7$ matrix, alternate rows and columns can be excluded: rows 2, 4, and
6, and columns 2, 4 and 6 because they correspond to the monomials $x^{2}$,
$x^{4}$ and $x^{6}$ and their representations in the basis
$\\{T_{1}(x),\ldots,T_{7}(x)\\}$

The matrix $M_{MH}$ has the same pattern of zero and non-zero elements as
$M_{TM}$, so that elements that are zero in the upper triangle can be excluded
from both matrices.

After applying case 1 and 4, we obtain the compressed matrices which have
$\frac{1}{4}$ of the total elements, and $\frac{5}{32}$ of them are included.

$\displaystyle\begin{bmatrix}1&\frac{3}{4}&\frac{5}{8}&\frac{35}{64}\\\ \\\
0&\frac{1}{4}&\frac{5}{16}&\frac{21}{64}\\\ \\\
0&0&\frac{1}{16}&\frac{7}{64}\\\ \\\
0&0&0&\frac{1}{64}\end{bmatrix}\begin{bmatrix}2&-12&\phantom{-}120&-1680\\\
\\\ 0&\phantom{-}8&-160&\phantom{-}3360\\\ \\\
0&\phantom{-}0&\phantom{-}32&-1344\\\ \\\
0&\phantom{-}0&\phantom{-}0&128\end{bmatrix}=\begin{bmatrix}2&-6&\phantom{-}20&\phantom{-}70\\\
\\\ 0&\phantom{-}2&-30&\phantom{-}462\\\ \\\
0&\phantom{-}0&\phantom{-}2&-70\\\ \\\
0&\phantom{-}0&\phantom{-}0&\phantom{-}2\end{bmatrix}$

From equation (16), the number of included elements in each matrix after the
optimization is $\frac{1}{8}(8\times 10)=10$. From the third column of the
last matrix, for example,

$\displaystyle H_{5}(x)=$ $\displaystyle
2T_{5}(x)-30T_{3}(x)+20T_{1}(x),\mbox{ i.e.}$ $\displaystyle
32x^{5}-160x^{3}+120x=$ $\displaystyle
2(16x^{5}-20x^{3}+5x)-30(4x^{3}-3x)+20x.$

Similarly, if we we want to change basis for polynomials of odd degree, this
is an example of cases 2 and 4 in §5.1 where the last column and row of the
matrices $M_{TM}$ and $M_{MH}$ are excluded, and also elements that are zero
in the upper triangles. This gives

$\displaystyle\begin{bmatrix}1&\frac{1}{2}&\frac{3}{8}&\frac{5}{16}\\\ \\\
0&\frac{1}{2}&\frac{1}{2}&\frac{15}{32}\\\ \\\ 0&0&\frac{1}{8}&\frac{3}{16}\\\
\\\ 0&0&0&\frac{1}{32}\end{bmatrix}\begin{bmatrix}1&-2&\phantom{-}12&-120\\\
\\\ 0&\phantom{-}4&-48&\phantom{-}720\\\ \\\
0&\phantom{-}0&\phantom{-}16&-480\\\ \\\
0&\phantom{-}0&\phantom{-}0&\phantom{-}64\end{bmatrix}=\begin{bmatrix}1&0&-6&\phantom{-}80\\\
\\\ 0&\phantom{-}2&-16&\phantom{-}150\\\ \\\
0&\phantom{-}0&\phantom{-}2&-48\\\ \\\
0&\phantom{-}0&\phantom{-}0&\phantom{-}2\end{bmatrix}$

From the fourth column of the last matrix, for example, we have

$\displaystyle H_{6}(x)=$ $\displaystyle
2T_{6}(x)-48T_{4}(x)+150T_{2}(x)+80T_{0}(x)$ $\displaystyle=$ $\displaystyle
64x^{6}-480x^{4}+720x^{2}-120.$

because the columns corresponding to monomials of even degree can be excluded,
i.e. columns 2, 4, and 6 The vector space we use has the following basis
represented by the monomials: $B=\\{x,x^{3},x^{5},x^{7}\\}$. The bases
$\\{H_{1}(x),H_{3}(x),H_{5}(x),H_{7}(x)\\}$ and
$\\{T_{1}(x),T_{3}(x),T_{5}(x),T_{7}(x)\\}$ are both triangular bases with
respect to $B$.

From [9, equation 18.5.12], we have

$H_{n}(x)=n!\sum_{l=0}^{\lfloor\frac{n}{2}\rfloor}\frac{{(-1)}^{l}{(2x)}^{n-2l}}{l!(n-2l)!}$
(22)

For this example, it gives

$\alpha_{2}(n,k)=\left\\{\begin{array}[]{ll}n!\frac{(-1)^{\frac{k}{2}}2^{n-k}}{\frac{k}{2}!(n-k)!}&\mbox{if
$k$ is even}\\\ 0&\mbox{if $k$ is odd.}\end{array}\right.$

where $0\leq k\leq n$ because $H_{n}(x)$ has definite parity.

From equation (20) we obtain,

$\beta_{2}(n,k)=n!\frac{(-1)^{k}2^{n-2k}}{k!(n-2k)!}$

where $0\leq k\leq\lfloor\frac{n}{2}\rfloor$.

This gives the following change of basis matrix $M_{BH}$:

$\displaystyle\begin{bmatrix}2&-12&\phantom{-}120&-1680\\\ \\\
0&\phantom{-}8&-160&\phantom{-}3360\\\ \\\
0&\phantom{-}0&\phantom{-}32&-1344\\\ \\\
0&\phantom{-}0&\phantom{-}0&\phantom{-}128\end{bmatrix}$

From Mason and Handscomb [11, equation (2.14)], and equivalently Tao [20]

$x^{n}=2^{1-n}{\sum_{k=0}^{\lfloor\frac{n}{2}\rfloor}}{}^{{}^{\prime}}{{n}\choose{k}}T_{n-2k}(x)$
(23)

where the primed sum means that its $k$th term is halved if $n$ is even and
$k=\frac{n}{2}$.

We have

$\alpha_{1}(n,k)=\left\\{\begin{array}[]{ll}2^{1-n}{n\choose{\frac{k}{2}}}&\mbox{if
$k$ is even}\\\ 0&\mbox{if $k$ is odd.}\end{array}\right.$

where $0\leq k\leq n$ and $n$ is odd.

From equation (20), it follows that

$\beta_{1}(n,k)=2^{1-n}{n\choose k}$

where $0\leq k\leq\lfloor\frac{n}{2}\rfloor$.

This gives change of basis matrix $M_{TB}$:

$\displaystyle\begin{bmatrix}1&\frac{3}{4}&\frac{5}{8}&\frac{35}{64}\\\ \\\
0&\frac{1}{4}&\frac{5}{16}&\frac{21}{64}\\\ \\\
0&0&\frac{1}{16}&\frac{7}{64}\\\ \\\ 0&0&0&\frac{1}{64}\end{bmatrix}$

We have $M_{TH}=M_{TB}M_{BH}$:

$\displaystyle\begin{bmatrix}2&-6&\phantom{-}20&\phantom{-}70\\\ \\\
0&\phantom{-}2&-30&\phantom{-}462\\\ \\\ 0&\phantom{-}0&\phantom{-}2&-70\\\
\\\
0&\phantom{-}0&\phantom{-}0&\phantom{-}2\end{bmatrix}=\begin{bmatrix}1&\frac{3}{4}&\frac{5}{8}&\frac{35}{64}\\\
\\\ 0&\frac{1}{4}&\frac{5}{16}&\frac{21}{64}\\\ \\\
0&0&\frac{1}{16}&\frac{7}{64}\\\ \\\
0&0&0&\frac{1}{64}\end{bmatrix}\begin{bmatrix}2&-12&\phantom{-}120&-1680\\\
\\\ 0&\phantom{-}8&-160&\phantom{-}3360\\\ \\\
0&\phantom{-}0&\phantom{-}32&-1344\\\ \\\
0&\phantom{-}0&\phantom{-}0&128\end{bmatrix}$

From the third column,

$\displaystyle H_{5}(x)=$ $\displaystyle
2T_{5}(x)-30T_{3}(x)+20T_{1}(x),\mbox{ i.e.}$ $\displaystyle
32x^{5}-160x^{3}+120x=$ $\displaystyle
2(16x^{5}-20x^{3}+5x)-30(4x^{3}-3x)+20x.$

The columns of $M_{TH}$ for any $n>0$ where $n$ is odd can be found by
applying equation (6). The maximum degree of the basis polynomials is
$m=2n-1$.

$\displaystyle\beta_{3}(n,k)=$
$\displaystyle\sum_{v=0}^{k}\beta_{1}(n-2v,k-v)\beta_{2}(n,v)$
$\displaystyle=$
$\displaystyle\sum_{v=0}^{k}2^{1-n+2v}{{n-2v}\choose{k-v}}\frac{n!{(-1)}^{v}2^{n-2v}}{v!(n-2v)!}$
$\displaystyle=$ $\displaystyle
2\sum_{v=0}^{k}{(-1)}^{v}\frac{n!}{v!\;(k-v)!\;(n-k-v)!}$

where $0\leq k\leq\lfloor\frac{n}{2}\rfloor$.

This gives

$H_{n}(x)=\sum_{k=0}^{\lfloor\frac{n}{2}\rfloor}\beta_{3}(n,k)T_{n-2k}(x)$
(24)

where $n>0$ and $n$ is odd.

##  7 Conclusion

Change of basis in finite vector spaces has numerous significant and
widespread applications. We show in Theorem 1 that in general, the change of
basis matrices of a set of $m$ bases of a finite vector space is a connected
groupoid of order $m^{2}$. The groupoid function is matrix multiplication
between matrices that have an exchange basis, following Definition 3. These
change of basis matrices represent transformations between bases and can be
typed with simple types.

We are concerned with finding algebraic expressions for the elements of such
change of basis matrices. The groupoid function leads to a general method via
a vector dot product for this. Five optimizations of it are defined.

Firstly, Definition 4 of triangular basis specializes change of basis matrices
to upper triangular ones. The algebraic expressions in change of basis
matrices can be expressed by coefficient functions, $\alpha(n,k)$, following
Definition 4. Equation (6) provides the coefficient functions in this case.
This optimization has similarities to that by Schuster [17] and Dilts [6] in
their algorithms that use spherical harmonics [2].

Four additional optimizations of the evaluation of $\alpha(n,k)$ were defined
in Section 5.1. They exclude elements that are known to be $0$ in the
evaluation of vector dot products, or exclude rows and columns from a change
of basis matrix. Expressions are given for the number of included elements of
a change of basis matrix.

These optimizations are applicable, for example, in the context of bases that
are classical orthogonal polynomials and when the parity of basis polynomials
is relevant, such as approximating even or odd functions. Examples of the
optimizations are given with a change of basis from Hermite polynomials
$H_{n}(x)$ of odd parity to Chebyshev polynomials $T_{n}(x)$. Another example
is a change of basis from Laguerre polynomials $L_{n}(x)$, that do not have
definite parity, to $T_{n}(x)$.

## Acknowledgment

I am grateful to the College of Engineering & Computer Science at The
Australian National University for research support.

## References

  * [1] Abramowitz, M., Stegun, I.A. (Eds.) (1972). Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables. 10$th$ printing, National Bureau of Standards, Department of Commerce, USA.
  * [2] Boyd, J.P. (2001). Chebyshev and Fourier Spectral Methods. Second revised ed., Mineola, NY:Dover.
  * [3] Brandt, H. (1926). Über eine Verallgemeinerung des Gruppenbegriffes. Math. Ann. 96: 360–366.
  * [4] Brown, R. (1987). From groups to groupoids: a brief survey. Bull. London Math, Soc. 19: 113–134.
  * [5] Church, A. (1940). A formulation of the simple theory of types. J. Symbolic Logic. 5(2): 56–58.
  * [6] Dilts, G.A. (1985). Computation of spherical harmonic expansion coefficients via FFT’s. J. Comput. Phys. 57: 439–453.
  * [7] Hale, N., Olver, S. (2018). A fast and spectrally convergent algorithm for rational-order fractional integral and differential equations. SIAM J. Sci. Comput. 40: A2456–A2491.
  * [8] Hale, N., Townsend, A. (2014). A fast, simple and stable Chebyshev-Legendre transform using an asymptotic formula. SIAM J. Comput. 35(1): A148–A167.
  * [9] T.H. Koornwinder, R. Wong, R. Koekoek, R.F. Swarttouw. (2020). Chapter 18 Orthogonal Polynomials, §18.18 (iv) Connection Formulas. Digital Library of Mathematical Functions, National Institute of Standards and Technology, U.S. Department of Commerce. https://dlmf.nist.gov/18.18#iv.
  * [10] Fortunato, D., Hale, N.,Townsend, A. (2021). The ultraspherical spectral element method. J. Comput. Phys. 436: 110087.
  * [11] Mason, J.C., Handscomb, D.C. (2002). Chebyshev Polynomials. New York: Chapman and Hall/CRC.
  * [12] Lewanowicz, S. (2002). Construction of recurrences for the coefficients of expansions in q-classical orthogonal polynomials. J. Comput. and Appl. Math. 153: 295–309.
  * [13] Olver, S., Townsend, A. (2013). A fast and well-conditioned spectral method. SIAM Rev. 55: 462–489.
  * [14] Pennebaker, W.B., Mitchell, J.L. (1993). JPEG: Still Image Data Compression Standard. Norwell, Massachusetts: Kluwer Academic.
  * [15] Salzer, H.E. (1973). A recurrence scheme for converting from one orthogonal expansion into another. Commun. ACM. 16(11): 705–707.
  * [16] Poole, D. (2015) Linear Algebra: A Modern Introduction, Fourth ed., Stamford, CT: Cengage Learning.
  * [17] Schuster, A. (1902). On some definite integrals and a new method of reducing a function of spherical co-ordinates to a series of spherical harmonics. Proc. R. Soc. Lond., 71: 97–101.
  * [18] Strang, G. (1993). Wavelet transforms versus Fourier transforms. Bull. Amer. Math. Soc. 28: 288–305.
  * [19] Szegö, G. (1975). Orthogonal Polynomials. Providence, Rhode Island: American Mathematical Society, Fourth ed.
  * [20] Tao, T. (2019). Conversions between standard polynomial bases. https://terrytao.wordpress.com/2019/04/07/conversions-between-standard-polynomial-bases/.