Practical symmetric equivalent to QR factorization updates As we know, the QR-factorization $Q\cdot R=A$ of any real symmetric $n \times n$ matrix $A$ with full rank is unconditionally numerically stable. Further, when A is rank-1-updated, the factorization can be updated in $\mathcal{O}(n^2)$, and the factorization remains stable after the update as well!
Now, when $A$ is symmetric, I seek a decomposition with all the same properties, plus that the factorization itself is symmetric. So to summarize, these are the properties of a factorization that I seek:

*

*The factorization is unconditionally numerically stable (i.e., no conditions on inertia, spectrum, norm, M-property, reodering, growth-factor, etc, are permitted to be imposed on $A$ whatsoever).

*The factorization is inherently symmetric (e.g., $Q^T \cdot R^T \cdot D \cdot R \cdot Q$), i.e., exact multiplication of the factors yields a symmetric matrix.

*The factorization can be updated in $\mathcal{O}(n^2)$ and remains stable afterwards.

Remark 1: For general symmetric $A$, no assertions can be given on the stability of LDL-factorizations. (In some cases, reorderings do exist, but upon rank-1-update, the matrix would have to be reordered from the start, thus assertions on the stability of the factorization after the rank-1-update do not exist.
Remark 2: I am likewise interested in a result that such sought decomposition cannot exist.
 A: It may be difficult to meet all your criteria but here's an attempt.
This is a bit lower-level than Federico Poloni's suggestion to use the eigenvalue factorization.
The Lanczos algorithm computes a unitary matrix $Q$ and a symmetric, tridiagonal matrix $T$ such that
$$A = QTQ^*$$
using $n$ matrix-vector multiplies.
I'll assume that you have a numerically stable implementation of the Lanczos algorithm but see below.
In any case, if $A' = A + \alpha uu^*$, then if we let $z = Q^*u$,
$$A' = QTQ^* + \alpha uu^* = Q(T + \alpha zz^*)Q^*.$$
Now of course the matrix $T + \alpha zz^*$ is no longer tridiagonal.
But multiplying it by a vector only requires $\mathscr{O}(n)$ operations.
So we can compute the tridiagonal factorization
$$T + \alpha zz^* = PSP^*$$
with $P$ unitary and $S$ tridiagonal in only $\mathscr{O}(n^2)$.
More or less the same works if you did a rank-$k$ update so long as $k \ll n$.
Putting it all together now, the desired rank-1 update is
$$A' = QPS(QP)^*.$$
Now as I alluded to above the Lanczos algorithm has quite subtle stability properties.
The columns of $Q$ are guaranteed to be orthogonal in real arithmetic, but in floating point arithmetic they will fail to remain exactly orthogonal and can even become linearly dependent.
The worst part about it is that the loss of orthogonality is greatest whenever one of the eigenvectors of the partial factorization grows close to one of the eigenvectors of $A$.
So in a sense the algorithm sabotages itself.
The remedy for this is to re-orthogonalize the Lanczos vectors, but if you reorthogonalize all of them, we're back at $\mathscr{O}(n^3)$ again.
There are partial reorthogonalization strategies that bring this back down.
I've implemented them and found them to be quite finicky but your mileage may vary.
My point here is that the Lanczos algorithm might fulfill all your requirements or only some of them.
In any case, almost all methods for computing the full eigendecomposition require first reducing the matrix to tridiagonal form.
If you want to read more, you can consult The Symmetric Eigenvalue Problem or Do We Understand the Symmetric Lanczos Algorithm Yet?, both by Parlett, or Numerical Methods for Large Eigenvalue Problems by Saad.
Finally, and this is a little pedantic, but I'd say that there are numerically stable algorithms for computing the QR factorization, not that the factorization itself is stable.
There are numerically unstable algorithms for computing the QR factorization as well!
For example, the Householder approach (orthogonal triangularization) is stable while Gram-Schmidt (triangular orthogonalization) is not.
A: [EDIT: not working in fact because the update of $Q$ cannot be merged efficiently, see comments] A simple eigendecomposition $A=QDQ^*$ should work, since it can be updated in $O(n^2)$.
